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:

• Nonterminals are written in plain text.
• Terminals are written in blue color.
• An optional element is indicated by surrounding squared brackets [ and ].
• A repetition element (can occur arbitrarily often, including zero times) is indicated by surrounding curly braces { and }.
• A permutation element is indicated by ∏ and surrounding brackets ( and ).

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}
}