# 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 ).

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