<commit_before>:- module(nfa,
	  [
	   nfa_dfa/2
	  ]).

:- use_module(library(ugraphs)).
:- use_module(library(ordsets)).

:- dynamic arc/3, dfa_arc/3, state/3, egraph/1, dfa_state/3.


nfa_dfa(nfa(_, NFA_Arcs, NFA_S0, NFA_Final),
	dfa(DFA_States, DFA_Arcs, DFA_Initial, DFA_Final)
       ) :-

	% Initialize DB
	retractall(egraph(_)),
	retractall(arc(_, _, _)),
	retractall(dfa_arc(_, _, _)),
	retractall(state(_, _, _)),
	retractall(dfa_state(_, _, _)),

	forall(member(Arc, NFA_Arcs), assertz(Arc)),

	% assert e-graph for closure calculation
	assert_egraph,

	% calculate and assert the closure of start state
	closure(NFA_S0, S0_Closure),
	S0_Closure_Term =.. [compound_state|S0_Closure],
	assertz(state(S0_Closure_Term, 0, start)),

	% the main part
	list_to_ord_set(NFA_Final, NFA_Final_Set),
	resolve_unmarked_states(NFA_Final_Set),

	state_renumbering(DFA_States, DFA_Arcs,
			  DFA_Initial, DFA_Final).


state_renumbering(States, Arcs, Initial, Final) :-

	% enumerate new states
	findall(dfa_state(Old, New, M),
		state(Old, _, M),
		States_C),
	bagof(New,
	      Old^M^member(dfa_state(Old, New, M), States_C),
	      States),
	length(States, N_States),
	numlist(1, N_States, States),
	% assert the translation table
	forall(member(S, States_C), assertz(S)),

	% renumerate states in arcs
	findall(
	    arc(New_From, Sym, New_To),
	    (   dfa_arc(Old_From, Sym, Old_To),
		dfa_state(Old_From, New_From, _),
		dfa_state(Old_To, New_To, _)
	    ),
	    Arcs ),

	dfa_state(_, Initial, start),
	!, % only one start state is possible
	findall(S, dfa_state(_, S, final), Final).


resolve_unmarked_states(NFA_Final) :-

	(
	    retract(state(T, 0, M))
	->
	    assertz(state(T, 1, M)),  % mark the state
	    process_transitions(NFA_Final, T),
	    resolve_unmarked_states(NFA_Final)
	;
	    true
	).

process_transitions(NFA_Final, T) :-

	T =.. [_|NFA_States],
	(   next_dest(NFA_States, Dest, Symbol),
	    closures(Dest, Closure),
	    (	ord_intersect(NFA_Final, Closure)
	    ->	M = final
	    ;	M = o
	    ),
	    Closure_Term =.. [compound_state|Closure],
	    (   state(Closure_Term, _, _)
	    ->  true
	    ;   assertz(state(Closure_Term, 0, M)) %add unmarked
	    ),
	    assert(dfa_arc(T, Symbol, Closure_Term)),<commit_msg>Fix nfa->dfa in a case the initial state is in final states<commit_after>:- module(nfa,
	  [
	   nfa_dfa/2
	  ]).

:- use_module(library(ugraphs)).
:- use_module(library(ordsets)).

:- dynamic arc/3, dfa_arc/3, state/3, egraph/1, dfa_state/3.


nfa_dfa(nfa(_, NFA_Arcs, NFA_S0, NFA_Final),
	dfa(DFA_States, DFA_Arcs, DFA_Initial, DFA_Final)
       ) :-

	% Initialize DB
	retractall(egraph(_)),
	retractall(arc(_, _, _)),
	retractall(dfa_arc(_, _, _)),
	retractall(state(_, _, _)),
	retractall(dfa_state(_, _, _)),

	forall(member(Arc, NFA_Arcs), assertz(Arc)),

	% assert e-graph for closure calculation
	assert_egraph,

	% calculate and assert the closure of start state
	closure(NFA_S0, S0_Closure),
	S0_Closure_Term =.. [compound_state|S0_Closure],
	assertz(state(S0_Closure_Term, 0, start)),

	% the main part
	list_to_ord_set(NFA_Final, NFA_Final_Set),
	resolve_unmarked_states(NFA_Final_Set),

	state_renumbering(DFA_States, DFA_Arcs,
			  DFA_Initial, DFA_Final0),

	% check whether the start state is also final
	(   memberchk(NFA_S0, NFA_Final)
	->  DFA_Final = [DFA_Initial|DFA_Final0]
	;   DFA_Final = DFA_Final0
	).


state_renumbering(States, Arcs, Initial, Final) :-

	% enumerate new states
	findall(dfa_state(Old, New, M),
		state(Old, _, M),
		States_C),
	bagof(New,
	      Old^M^member(dfa_state(Old, New, M), States_C),
	      States),
	length(States, N_States),
	numlist(1, N_States, States),
	% assert the translation table
	forall(member(S, States_C), assertz(S)),

	% renumerate states in arcs
	findall(
	    arc(New_From, Sym, New_To),
	    (   dfa_arc(Old_From, Sym, Old_To),
		dfa_state(Old_From, New_From, _),
		dfa_state(Old_To, New_To, _)
	    ),
	    Arcs ),

	dfa_state(_, Initial, start),
	!, % only one start state is possible

	findall(S, dfa_state(_, S, final), Final).



resolve_unmarked_states(NFA_Final) :-

	(
	    retract(state(T, 0, M))
	->
	    assertz(state(T, 1, M)),  % mark the state
	    process_transitions(NFA_Final, T),
	    resolve_unmarked_states(NFA_Final)
	;
	    true
	).

process_transitions(NFA_Final, T) :-

	T =.. [_|NFA_States],
	(   next_dest(NFA_States, Dest, Symbol),
	    closures(Dest, Closure),
	    (	ord_intersect(NFA_Final, Closure)
	    ->	M = final
	    ;	M = o
	    ),
	    Closure_Term =.. [compound_state|Closure],
	    (   state(Closure_Term, _, _)
	    ->  true
	    ;   assertz(state(Closure_Term, 0, M)) %add unmarked
	    ),
	    assert(dfa_arc(T, Symbol, Closure_Term)),
{'fraction_non_alphanumeric': 0.14109384975526706, 'fraction_numerical': 0.008086826984464779, 'mean_word_length': 3.8958333333333335, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6392378', 'n_tokens_mistral': 2063, 'n_tokens_neox': 1912, 'n_words': 348}