Determinization

The determinization algorithm I used is a subset-construction algorithm. For a given automaton (the `input' automaton) the construction computes an equivalent, but deterministic automaton (the `output' automaton). The algorithm maintains an agenda of states (of the output automaton) whose successors need to be computed, a table of states (of the output automaton) that have already been processed, a list of transitions (of the output automaton), and a list of final states (of the output automaton). A state of the output automaton is a subset of states from the input automaton. For each state on the agenda, the procedure computes all transitions that are possible leaving that state. If new states arise, then these states are added to the agenda.

The relation treat_start_states computes the set of states reachable without input consumption from the start states of the input automaton. This set of states from the input automaton constitutes the single start state of the output automaton. This start state is added to the list of final states if one of the input states is a final state. The initial agenda for the subset construction process contains this start state as a single element.

determinize([Start],Finals,Transitions) :- treat_start_states(Start,Table,Finals0,Finals), closure([Start],Table,Finals0,Transitions).

(33)

The relation closure recursively processes the agenda. Its arguments are respectively the list of states to be processed, the table of states already processed, the resulting list of final states, and the resulting list of transitions. If the agenda is empty, then the process finishes. Otherwise the first state of the agenda is considered and all transitions leaving this state are computed. Any new states that result are added to the agenda.

closure([],_table,[],[]). % no more states, finished. closure([H|Agenda0],Table0,Tr,Fin) :- findall(NTrans,new_transition(H,NTrans),Transs), add(Transs,Agenda0,Agenda,Table0,Table,Tr0,Tr,Fin0,Fin), closure(Agenda,Table,Tr0,Fin0).

(34)

The relation new_transition defines what a possible transition is. The relation consists of a state (from the output automaton) and all transitions that are possible with this state as a source state.

new_transition(Begins,trans(Begins,Sym,Ends)) :- setof(End,a_trans(Begins,Sym,End),Ends).

(35)

a_trans(Begins,Sym,End) :- member(Begin,Begins), trans(Begin,Sym,Mid), p_tr_jump(Mid,End). % End is jump-reachable from Mid

(36)

The p_tr_jump relation consists of pairs of states from the input automaton such that the second state can be reached without reading any symbols from the first state (reflexive and transitive closure of the jump relation).

The relation add/9 inspects the given list of transitions for new target states. These transitions are added to the list of transitions. Each new state (i.e. not yet in the table) is added to the agenda and to the table (and to the list of final states if this state contains a final state of the input automaton). This concludes the presentation of the determinization algorithm.