Both Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA) can be represented using transition tables and state diagrams.
- Transition Tables:
a. DFA Transition Table:
In a DFA transition table, each row represents a state of the DFA, and each column represents a symbol from the alphabet. The entries in the table indicate the next state the DFA transitions to when it reads a particular symbol in a particular state.
Example DFA Transition Table:
State 0 1 q0 q1 q2 q1 q2 q1 q2 q0 q2 This table indicates, for example, that if the DFA is in state q0 and reads the symbol ‘0’, it transitions to state q1.
b. NFA Transition Table:
In an NFA transition table, each row represents a state of the NFA, and each column represents a symbol from the alphabet. However, unlike in a DFA transition table, the entries in an NFA transition table can contain multiple next states or even sets of next states for each state-symbol combination.
Example NFA Transition Table:
State 0 1 q0 q0,q1 q1 q1 q2 q1 q2 q0,q2 q2 This table indicates, for example, that if the NFA is in state q0 and reads the symbol ‘0’, it could transition to either q0 or q1.
- State Diagrams:
State diagrams visually represent the states, transitions, and accept states of finite automata. In a state diagram:
- States are represented by circles or nodes.
- Transitions between states are represented by arrows labeled with input symbols.
- Accept states (final states) are typically denoted by double circles or some other distinguishing feature.
a. DFA State Diagram:
In this DFA state diagram:
- Circles represent states (q0, q1, q2).
- Arrows represent transitions labeled with input symbols (0, 1).
- The double circle indicates the accept state (q2).
b. NFA State Diagram:
In this NFA state diagram:
- Circles represent states (q0, q1, q2).
- Arrows represent transitions labeled with input symbols (0, 1).
- The double circle indicates the accept state (q2).
- Note that there are ε-transitions (epsilon transitions) represented by unlabeled arrows. These transitions don’t consume any input symbol and are allowed to take the machine from one state to another.