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.