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 the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
