-f Minimizing Deterministic Finite. Automata: We can partition tlie states of any DFA into groups of mutually indistinguishable states. Members of two different gioups are always distinguishable. If we replac:e each group by a single state, we get an equivalent DF.A that has as few states as any DFA for the sam<? language.

4.6 References for Chapter 4

Except for the obvious closure properties of regular expressions - union, concatenation, and star - that were shown by Kleene [6], almost all results about closure properties of the regular languages mimic similar results about context-free languages (the class of languages we study in the next chapters). Thus, the ]mmping lemma for regular languages is a simplification of a corresponding result for context-free languages by Bar-Hillel, Perles, and Shamir [1]. The same paper indirectly gives us several of the other closure properties shown here. Howwer, the closure- under inverse homomorphism is fiom [2].

The quotient operation introduced in Exercise 4.2.2 is from [3]. In fact, that papcT talks about a more general operation where in place of a single sjinbol a is any regular language. The series of operations of the partial removal type, starting with Exercise 4,2.8 on the first halves of strings in a regular language, began with [8]. Seiferas and McNaughton [9] worked out the general case of when a removal operation preserves regular languages.

The original decision algorithms, such as emptiness, finiteness, and membership f(jr regidar languages, are from [7]. Algorithms for mimnuzing the. states of a DFA appear there; and in [-5], The most efficient algorithm for finding the minimum-state DFA is in [4j.

1. Y. Bar-Hillel, M, Perles, and E. Shamir, On formal properties of simple phras(vstnicture grammars, Z. Phonelik. Sprachwiss. Kom?nunikations-forsdi. 14 (1961), pp, 143 172.

2, S. Ginsburg and G. Rose, Operations which preserve definabifity in languages. ,/, ACM 1И:2 (1963), pp. 175-195.

3, S, Ginsburg and E. H, Spanier, Quotients of context-free hmguages, J. ACM 10:4 (1963), pp. 487-492.

4, J, E, Hopcroft, An nlogri algorithm for minimizing the .states in a finite automaton, in Z. Kohavi (ed,) The Theory of Machines and Computa-tinnS; -Aicademic Press, New York, pp, 189-196,

5. D, A. Huffman, The synthesis of sequential switching circuits, ,7. Franklin Inst. 257:3-4 (1954), pp. 161 190 and 275-303.

6. S. C. Kleene, Representation of events in nerve nets and finite automata, in C- E. Shannon and J. McCarthy, Automata Studies, Princeton Univ, Press, 1956, pp. 3-42.

4.6. REFERENCES FOR CHAPTER 4 167

7. E. F. Moore, Gedanken experiments on sequtential machines, in C. E. Shannon and J. McCarthy, Automata Studies, Princeton Univ. Pre, 1956, pp. 129-153.

8. R. E. Stearns and J. Hartmanis, Regularity-preserving moddications of regidar exprsions, Information and Control 6:1 (1963), pp. 55-69.

9. J. I. Seiferas and R. McNaughton, Regularity-preserving modifications, Thearetieal Computer Science 2:2 (1976), pp. 147-154.

Chapter 5

Context-Free Grammars and Languages

We now turn onr attention away from the r(;gular languages to a larger class of languages, called the context-free languages. These languages have a natural, recursive notation, called context-free grammars. Context-free grammars have played a central role in comjiiler technology since the 1960s; tiiey turned the implementation of parsers (functions that discover the structure of a program) from a time-consuming, ad-hoc implementation task into a. routine job that can be done in an afternoon. More recently, the context-free grammar has been used to describe document formats, via the so-called document-type definition (DTD) that is used in the XML (extensible markup language) cornmimity for information exchange on the Web,

In this chapter, we introduce the context-free grammar notation, and shf)w how grammars define languages. Wo discuss the parse tree, a picture of the structure that a grammar places on the strings of its language. The parse tree is tlu! product of a. parser fijr a progranuning language and is the way that the structure of programs is normally captuK-d.

There is an automaton-like notation, called the pushdown automaton, that also describes all and only the context-free languages; we intrcjduce the pushdown automaton in Chapter 6, While less imptjrtant than finite automata, we shall find the pushdown automaton, especially its equivalence to context-free grammars as a language-defining mechanism, to be quite useful when we explore the closure and decision properties of the context-free languages in Chapter 7,

5.1 Context-Free Grammars

We shall begin by introducing the context-free grammar notation informally. After seeing some of the important capabilities of these grammars, we offer formal definitions. We show how to define a grfinniiar formally, and introduce;