Chapter 4. Finite State Automata: Characterization, Properties, and Decidability

In this chapter, the equivalence between right linear grammars and finite state automata (FSA) is proved. The pumping lemma for regular sets is considered, and is used to give a method for showing a language not to be regular. We also consider some basic closure properties and decidability results.

FSA and Regular Grammars

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.