4- Operations That Preserve Context-Free Languages: The CFLs are dosed under substitution, union, concatenation, closure (star), reversal, and inverse homomorphisms. CFLs are not closed mider intersection or complementation, but the intersection of a CFL and a regular language is always a CFL.

♦ Testing Emptiness of a CFL: Given a CFG, there is an algorithm to tell \vhether it generates any strings at all. A careful implementation allows this test to be conducted in time that is proportional to the size of the grammar itself.

Testing Membership in a CFL: The Cocke-Younger-Kasami algorithm tells whether a given string is in a given context-free language. For a fixed CFL, this test takes time O(n), if n is the length of the string being tested.

7.6 References for Chapter 7

Chomsky normal form comes from [2]. Greibach normal form is from [4], although the construction outlined in Exercise 7.1.11 is due to M. C. PauU.

Many of the fundamental properties of context-free languages come from [1]. These ideas include the pumping lenuna, basic closure properties, and tests for simple questions such as emptiness and finiteness of a CFL. In addition [6] is the source for the nonclosure under intersection and complementation, and [3] provides additional closure results, including closure of the CFLs under inverse homomorphism. Ogdens lemma comes from [5].

The CYK algorithm has three known independent sources. J. Cockes work was circulated privately and never pubhshed. T. Kasamis rendition of essentially the same algorithm appeared only in an internal US-Air-Force memorandum. However, the work of D. Younger was published conventionally [7].

1. Y. Bar-Hillel, M. Perles, and E. Shamir, On formal properties of simple phrase-structure grammars, Z. Phonetik. Sprachwiss. Kommunikations-forsch. 14 (1961), pp. 143-172.

2. N. Chomsky, On certain formal properties of grammars, Information and Control 2:2 (1959), pp. 137-167.

3. S. Ginsburg and G. Rose, Operations which preserve definability in languages, J. ACM 10:2 (1963), pp. 175-195.

4. S. A. Greibach, A new normal-form theorem for context-free phrase structure grammars, J. ACJW 12:1 (1965), pp. 42-52.

5. W. Ogden, A helpful result for proving inherent ambiguity, Mathematical Systems Theory 2:3 (1969), pp. 31-42.

7.6. REFERENCES FOR CHAPTER 7 305

6. S. Scheinberg, Note on the boolean properties of context-free languages, Information and Control 3:4 {I960), pp. 372-375.

7. D. H. Younger, Recognition and parsuig of context-free laлguages in time n, Information and Control 10:2 (1967), pp. 189-208.

Chapter 8

Introduction to Turing Machines

In this chapter we change our direction significantly. Until now, we have been interested primarily in simple classes of languages and the ways that they can be used for relatively constrained problems, such as analyzing protocols, searching text, or parsing programs. Now, we shall start looking at the question of what languages can be defined by any computational device whatsoever. This question is tantamount to the question of what computers can do, since recognizing the strings in a language is a formed way of expressing any problem, and solving a problem is a reasonable surrogate for what it is that computers do.

We begin with an informal argument, using an assumed knowledge of С programming, to show that there are specific problems we cannot solve using a computer. These problems are called undecidable. We then introduce a venerable formalism for computers, called the Turing machine. While a Turing machine looks nothing like a PC, and would be grossly inefficient should some startup company decide to manufacture and sell them, the Turing machine long has been recognized as an accurate model for what any physical computing device is capable of doing.

In Chapter 9, we use the Turing machine to develop a theory of undecidable problems, that is, problems that no computer can solve. We show that a number of problems that are easy to express are in fact undecidable. An example is telling whether a given grammar is ambiguous, and we shall see many others.

8.1 Problems That Computers Cannot Solve

The purpose of this section is to provide an informal, C-programming-based introduction to the proof of a specific problem that computers cannot solve. The particular problem we discuss is whether the first thing a С program prints