Finite Automata Tool 
Grammar for Automata

Grammar for Automata

The here introduced grammar describes the exact syntax of how to write automata by hand. It can either be used to write an automaton in a normal text file or when creating a new automaton within the tool.

In that context we use a slightly modified version of the EBNF notation, say EBNF*, with the following conventions:

Note: The definition of trivial nonterminals concerning letters and digits are left out for obvious reasons.

Grammar in EBNF* notation:

automaton_grammar ::= dfa | nfa
dfa ::= DFA [automaton_name] = { dfa_stage }
nfa ::= NFA [automaton_name] = { nfa_stage }
dfa_stage ::= ∏([states] mandatory_choice_d initial_state [final_states])
nfa_stage ::= ∏([states] mandatory_choice_nd initial_state [final_states])
mandatory_choice_d ::= alphabet [transitions_d] | [alphabet] transitions_d
mandatory_choice_nd ::= alphabet [transitions_nd] | [alphabet] transitions_nd
states ::= states = { state {state} }
alphabet ::= alphabet = { entry {entry} }
transitions_d ::= transitions = { {transition_d} }
transitions_nd ::= transitions = { {transition_nd} }
initial_state ::= initial state = state
final_states ::= final states = { {state} }
state ::= state_def {state_def}
entry ::= entry_def {entry_def}
transition_d ::= state - entry -> state
transition_nd ::= state - entry -> set_states_option
set_states_option ::= state | { state {state} }
automaton_name ::= letter { letter | digit | _ | ( | ) | , }
state_def ::= letter | digit | _ | ( | ) | , | '
entry_def ::= letter | digit

Example:

Here is a concrete example of an NFA where state q1 has no outgoing transitions on input a, but two outgoing transitions on input b.
	
NFA myNFA = {
	states = {q0 q1 q2}
	alphabet = {a b}
	transitions = {
		q0-a->{q0 q1}
		q0-b->q1
		q1-b->{q0 q2}
		q2-a->q2
		q2-b->q2
	}
	initial state = q0
	final states = {q2}
}