Introduction to Formal Languages, Automata Theory and Computation

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

Theorem 4.1

If a language L is accepted by a finite non-deterministic automaton, then L can be accepted by a right linear grammar and conversely.

Proof. Let L be a language accepted by a finite non-deterministic automaton M = (K, Σ, δ, q₀, F) where K = {q₀, . . ., q_n}. If w ∊ L, then w is obtained by the concatenation of symbols corresponding to different ...