Select Page

Both Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA) can be represented using transition tables and state diagrams.

  1. 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.

  2. 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:

    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.