O'Reilly logo

Formal Languages and Automata Theory by K.V.N. Sunitha

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required