DFA - Deterministic finite automaton

FAdo's Class: FAdo.fa.DFA

A deterministic finite automaton is a 5-tuple $(Q, \Sigma, \delta, q_0, F)$ consisting of:

• A finite set of states $Q$
• A finite set of input symbols $\Sigma$, called the alphabet 
• A transition function $\delta : Q \times \Sigma \rightarrow Q$
• A start state $q_0 \in Q$
• A set of accepting states $F \subseteq Q$

Comments:

NFA - Nondeterministic finite automaton

FAdo's Class: FAdo.fa.NFA

A nondeterministic finite automaton is defined by a 5-tuple $(Q,\Sigma,\delta,q_0,F)$ consisting of:

• A finite set of states $Q$
• A finite set of input symbols $\Sigma$
• A transition function $\delta : Q \times \Sigma \rightarrow 2^Q$
• A  initial state $q_0\in Q$
• A set of final states $F \subseteq Q$

Where $2^Q$ is the power set of $Q$, i.e., the set of all subsets of $Q$. 

The NFA with $\epsilon$-moves replaces the transition function with one that allows the empty string as a possible input so that one has:

• A transition function $\delta : Q \times \Sigma \cup \{\epsilon\} \rightarrow 2^Q$

Comments:

IDFA - Incomplete deterministic finite automaton

FAdo's Class: FAdo.fa.DFA

An incomplete deterministic finite automaton is a 5-tuple $(Q,\Sigma,\delta,q_0,F)$ consisting of:

Comments: