Discrete Mathematics/Finite state automata

Formally, a Deterministc Finite Automaton (DFA) is a 5-tuple $D=(Q,\Sigma ,\delta ,s,F)$ where:

• Q is the set of all states.
  
• $\Sigma$ is the alphabet being considered.
  
• $\delta$ is the set of transitions, including exactly one transition per element of the alphabet per state.
  
• $s$ is the single starting state.
  
• F is the set of all accepting states.
  

For a DFA, $\delta$ can be viewed as a function from $Q\times \Sigma \to Q$.

Example: Consider the DFA ${A}=(\{p,q\},\{a,b\},\delta ,p,\{q\})$ with transitions given by table:

$\delta$	a	b
p	q	p
q	p	q

It is easy to verify that this DFA accepts the input "aaa".

Similarly, the formal definition of a Nondeterministic Finite Automaton is a 5-tuple $N=(Q,\Sigma ,\delta ,s,F)$ where:

• Q is the set of all states.
  
• $\Sigma$ is the alphabet being considered.
  
• $\delta$ is the set of transitions, with $\epsilon$ transitions and any number of transitions for any particular input on every state.
  
• $s$ is the single starting state.
  
• F is the set of all accepting states.
  

For a NFA, $\delta$ can be viewed as a function from $Q\times (\Sigma \cup \{\epsilon \})\to P(Q)$ where $P(Q)$ is the power set of $Q$.

Note that for both a NFA and a DFA, $s$ is not a set of states. Rather, it is a single state, as neither can begin at more than one state. However, a NFA can achieve similar function by adding a new starting state and epsilon-transitioning to all desired starting states.

The difference between a DFA and an NFA being the delta-transitions are allowed to contain epsilon-jumps(transitions on no input), unions of transitions on the same input, and no transition for any elements in the alphabet.

For any NFA $N$, there exists a DFA $D$ such that $L(N)=L(D)$