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 prope ...continues

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 t ...continues

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

Automata and Computability

Show that the collection of Turing-recognizable languages is closed under the operations of a. union. b. concatenation. c. star. d. intersection

Automata and Computability

Let c1 xn + c2xn-1+…+ cnx + cnx + cn + 1 be a polynomial with a root at x = x0. Let cmax be the largest absolute value of a cI . Show that (attached)

Automata and Computability

Let A = (attached) R and S are regular expressions and L(R)  L(S) . Show that A is decidable.

Automata and Computability

Let A = (attached) | R is a regular expression describing a language containing at least one string w that has 111 as a substring (i.e., w = x111y for some x and y)}. Show that A is decidable.

Automata and Computability

Let C be a language. Prove that C turing-recognizable if a decidable language D exists such that C = {x | y (x,y  D)}.