2
Finite Automata
In this chapter, we introduce the definition of Finite Automaton (FA) and also some real-time problems that can be solved using FA. Representation of FA is done using 5-tuple form, transition table and transition diagram. Definitions of non-deterministic and deterministic FAs are explained with examples and, further, how these automata act as language acceptor is elaborated. Equivalence of NFAs-with-ɛ to NFAs-without-ɛ, and equivalence of NFAs to DFAs are explained. Minimizing the given automaton using Myhill Nerode and π construction method, and testing the equivalence of two FAs are discussed. Moore and Mealy machines, which represent Finite Automaton with output, are explained with examples.
2.1 Finite-state Machine
The ...
Get Formal Languages and Automata Theory 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.
