Chapter 5. Finite State Automata with Output and Minimization

In this chapter, we consider Myhill-Nerode theorem, minimization of deterministic finite state automaton (DFSA) and finite state automaton (FSA) with output.

Myhill-Nerode Theorem

In an earlier chapter, we considered the examples of serial adder, parity machine, acceptor accepting {anbm|n,m ≥ 1}, and many more such examples. Consider the serial adder. After getting some input, the machine can be in ‘carry’ state or ‘no carry’ state. It does not matter what exactly the earlier input was. It is only necessary to know whether it has produced a carry or not. Hence, the FSA need not distinguish between each and every input. It distinguishes between classes of inputs. In the above case, the ...

Get Introduction to Formal Languages, Automata Theory and Computation now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.