Lecture No. 07

Dated: 14-03-2025

Table Encoding of Finite Automaton

A finite automaton¹ can be encoded as a table. This is called transition table.

	a	b
0	1	err
1	2	1
2	err	err

int finite_automaton () {

    int trans_table[NSTATES][NCHARS];
    int accept_states[NSTATES];

    int state = INITIAL;

    while (state != err) {
        c = input.read();
        if (c == EOF)
            break;

        state = trans_table[state][c];
    }

    return accept_states[state];
}

Non Deterministic Finite Automaton

Each regular expression² can be used to encode a token³ and is converted to a non deterministic finite automaton⁴ which are joined using \(\epsilon\) moves into a single deterministic finite automaton¹ which can later be encoded in a transition table.
A non deterministic finite automaton⁴ can have multiple transitions for one input in a given table.

Sometimes it might not even need an input character for transition.

The acceptance of non deterministic finite automaton⁴ for a given string⁴ is determined if it can reach a final state or not.

Deterministic Finite Automaton

This one has only one transition per input per state without \(\epsilon\) moves.
Both NFAs⁴ and DFAs¹ can recognize same set⁴ of languages⁵ though DFAs are easier but can be exponentially larger than NFAs. Therefore, NFAs are the key for automating RE -> DFA construction.

RE² → NFA⁴ Construction

The algorithm for regular expression² to DFA conversion is called Thompson's Construction. The algorithm appeared in CACM 1968. It works as follows

• Builds a NFA⁴ for each regular expression.²
• The NFAs⁴ are combined using \(\epsilon\) moves.
• The NFA⁴ is converted into DFA.¹
• The number of states is reduced in the DFA¹ using the Hopcroft’s algorithm.

Example

Consider a NFA⁴ for the regular expression² \(ab\).

NFA⁴ for \(a\)

NFA⁴ for \(b\)

NFA⁴ for \(ab\). The NFA⁴ for \(a\) appears first due to its precedence.

References

---

1. Read more about finite automaton. ↩↩↩↩↩

2. Read more about regular expressions. ↩↩↩↩↩

3. Read more about tokens. ↩

4. Read more about non deterministic finite automaton. ↩↩↩↩↩↩↩↩↩↩↩↩↩↩↩

5. Read more about languages. ↩