tailieunhanh - Ebook Introduction to automata theory, languages and computation (2nd edition): Part 2

(BQ) Part 2 book "Introduction to automata theory, languages and computation" has contents: Properties of context free languages, introduction to turing machines, undecidability, intractable problems, additional classes of problems. | Chapter 7 Properties of Context-Free Languages We shall complete our study of context-free languages by learning some of their properties. Our first task is to simplify context-free grammars these simplifications make it easier to prove facts about CFL s since we can claim that if a language is a CFL then it has a grammar in some special form. We then prove a pumping lemma for CFL s. This theorem is in the same spirit as Theorem for regular languages but can be used to prove a language not to be context-free. Next we consider the sorts of properties that we studied in Chapter 4 for the regular languages closure properties and decision properties. We shall see that some but not all of the closure properties that the regular languages have are also possessed by the CFL s. Likewise some questions about CFL s can be decided by algorithms that generalize the tests we developed for regular languages but there are also certain questions about CFL s that we cannot answer. Normal Forms for Context-Free Grammars The goal of this section is to show that every CFL without e is generated by a CFG in which all productions are of the form .4 - BC or A a where .4 B and c are variables and a is a terminal. This form is called Chomsky Normal Form. To get there we need to make a number of preliminary simplifications which are themselves useful in various ways 1. We must eliminate useless symbols those variables or terminals that do not appear in any derivation of a terminal string from the start symbol. 2. We must eliminate e -productions those of the form .4 e for some variable A. 255 256 CHAPTER 7. PROPERTIES OF CONTEXT-FREE LANGUAGES 3. We must eliminate unit productions those of the form A - B for variables A and B. Eliminating Useless Symbols We say a symbol X is useful for a grammar G V T P S if there is some derivation of the form s aX 3 w where w is in T . Note that X may be in either V or T and the sentential form aX0 might be the first or last in the .