Automata and Computability (A13)

Say that string x is a prefix of string y if a string z exists where xz = y and that x is a proper prefix of y if in addition x  y. In each of the following parts we define an operation on a language A. Show that the class of regular languages is closed under that operation. a. NOPREFIX (A) = {w  A| no proper prefix of w is a member of A} b. NOEXTEND (A) = {w  A| w is not the proper prefix of any string in A}

Automata and Computability

Let G be CFG in Chomsky normal form that contains b variables. Show that, if G generates some string using a derivation with more than b steps, L (G) is infinite.

Automata and Computability (A18)

Consider the language B = L (G), where G is the grammar given in Exercise 2.13 (page 121). The pumping lemma for context-free languages, Theorem 2.19 (page 115), states the existence of a pumping length p for B. What is the minimum value of p that works in the pumping lemma? Justify your answer.

Automata and Computability

A Turing machine with doubly infinite tape is similar to an ordinary Turing machine except that its tape is infinite to the left as well as to the right. The tape is initially filled with blanks except for the portion that contains the input. Computation is defined as usual except that the head never encounters an end to the tape as it moves leftward. Show that this type of Turing machine recognizes the class of Truing-recognizable languages.

Automata and Computability

Show that the collection of decidable languages is closed under the operations of a. union. b. concatenation. c. star. d. complementation. e. intersection