SKEDSOFT
Example of a NFA, Nondeterministic Finite Automata givenby
- Machine Definition M = (Q, sigma, delta, q0, F)
- Equivalent regular expression
- Equivalent state transition diagramand example tree of states for input string 0100011and an equivalent DFA, Deterministic Finite Automata for thefirst 3 states.
a) Machine DefinitionM = (Q, sigma, delta, q0, F)
Q = { q0, q1, q2, q3, q4 } the set of states
sigma = { 0, 1 } the input string alphabet
delta the state transition table
q0 = q0 the starting state
F = { q2, q4 } the set of final states (accepting when in
this state and no more input)
inputs
delta | 0 | 1 |
--------- --------- ---------
q0 | {q0,q3} | {q0,q1} |
q1 | phi | {q2} |
states q2 | {q2} | {q2} |
q3 | {q4} | phi |
q4 | {q4} | {q4} |
^ ^ ^
| | |
| --------- -- a set of states, phi means empty set
-- every state must be listed
b) The equivalent regular expression is (0 1)*(00 11)(0 1)* This NFA represents the language L = all strings over {0,1} that have at least two consecutive 0's or 1's.
c) Equivalent NFA state transition diagram.: Note that state q3 does not go anywhere for an input of 1. We use the terminology that the path "dies" if in q3 getting an input 1. The tree of states this NFA is in for the input 0100011
