Introduction to the theory of computation 3rd edition Michael Sipser - Solutions

Let A be a Turing-recognizable language consisting of descriptions of Turing machines, {〈M1〉, 〈M2〉, . . .}, where every Mi is a decider. Prove that some decidable language D is not decided by any decider Mi whose description appears in A. You may find it helpful to consider an
Let CCFG = {〈G, k〉| G is a CFG and L(G) contains exactly k strings where k ≥ 0 or k = ∞}. Show that CCFG is decidable.
Let C = {〈G, x〉| G is a CFG x is a substring of some y ∈ L(G)}. Show that C is decidable. An elegant solution to this problem uses the decider for ECFG.
Let E = {〈M〉| M is a DFA that accepts some string with more 1s than 0s}. Show that E is decidable. Theorems about CFLs are helpful here.
Let PALDFA = {〈M〉| M is a DFA that accepts some palindrome}. Show that PALDFA is decidable. Theorems about CFLs are helpful here.
Let BALDFA = {〈M〉| M is a DFA that accepts some string containing an equal number of 0s and 1s}. Show that BALDFA is decidable. Theorems about CFLs are helpful here.
A useless state in a pushdown automaton is never entered on any input string. Consider the problem of determining whether a pushdown automaton has any useless states. Formulate this problem as a language and show that it is decidable.
Say that an NFA is ambiguous if it accepts some string along two different computation branches. Let AMBIGNFA = {〈N〉| N is an ambiguous NFA}. Show that AMBIGNFA is decidable. One elegant way to solve this problem is to construct a suitable DFA and then run EDFA on it.
Let PREFIX-FREEREX = {〈R〉| R is a regular expression and L(R) is prefix-free}. Show that PREFIX-FREEREX is decidable. Why does a similar approach fail to show that PREFIX FREECFG is decidable?
Let S = {〈M〉| M is a DFA that accepts wR whenever it accepts w}. Show that S is decidable.
Let A and B be two disjoint languages. Say that language C separates A and B if A ⊆ C and B ⊆ C. Show that any two disjoint co-Turing-recognizable languages are separable by some decidable language.
Prove that the class of decidable languages is not closed under homomorphism.
Let C be a language. Prove that C is Turing-recognizable iff a decidable language D exists such that C = {x| ∃y (〈x, y〉 ∈ D)}.
Prove that EQDFA is decidable by testing the two DFAs on all strings up to a certain size. Calculate a size that works.
Let A = {〈R〉| 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.
Show that the problem of determining whether a CFG generates all strings in 1* is decidable. In other words, show that {〈G〉| G is a CFG over {0,1} and 1* ⊆ L(G)} is a decidable language.
Let Σ = {0,1}. Show that the problem of determining whether a CFG generates some string in 1 is decidable. In other words, show that{〈G〉| G is a CFG over {0,1} and 1* ∩ L(G) ≠ ⌀} is a decidable language.
Let A = {〈R, S〉| R and S are regular expressions and L(R) ⊆ L(S)}. Show that A is decidable.
Let A = {〈M〉| M is a DFA that doesn’t accept any string containing an odd number of 1s}. Show that A is decidable.
Let INFINITEPDA = {〈M〉| M is a PDA and L(M) is an infinite language}. Show that INFINITEPDA is decidable.
Let INFINITEDFA = {〈A〉| A is a DFA and L(A) is an infinite language}. Show that INFINITEDFA is decidable.
Review the way that we define sets to be the same size inDefinition 4.12 (page 203). Show that “is the same size” is an equivalence relation.
Let T = {(i, j, k)| i, j, k 2 N}. Show that T is countable.
Let B be the set of all infinite sequences over {0,1}. Show that B is uncountable using a proof by diagonalization.
Let X be the set {1, 2, 3, 4, 5} and Y be the set {6, 7, 8, 9, 10}. We describe the functions f : X → Y and g : X → Y in the following tables. Answer each part and give a reason for each negative answer. Aa. Is f one-to-one?b. Is f onto?c. Is f a correspondence?Ad. Is g one-to-one?e. Is g
Let ETM = {〈M〉| M is a TM and L(M) = ⌀}. Show that ETM, the complement of ETM, is Turing-recognizable.
Let AεCFG = {〈G〉| G is a CFG that generates ε}. Show that A"CFG is decidable.
Let ALLDFA = {〈A〉| A is a DFA and L(A) = Σ*}. Show that ALLDFA is decidable.
Consider the problem of determining whether a DFA and a regular expression are equivalent. Express this problem as a language and show that it is decidable.
Answer all parts for the following DFA M and give reasons for your answers.a. Is 〈M, 0100〉 ∈ ADFA?b. Is 〈M, 011〉 ∈ ADFA?c. Is 〈M〉 ∈ ADFA?d. Is 〈M, 0100〉 ∈ AREX?e. Is 〈M〉 ∈ EDFA?f. Is 〈M,M〉
Let A be the language containing only the single string s, whereIs A decidable? Why or why not? For the purposes of this problem, assume that the question of whether life will be found onMars has an unambiguous YES or NO answer. if life never will be found on Mars. S if life will be found on Mars
Let c1xn + c2xn−1 +· · ·+ cnx+cn+1 be a polynomial with a root at x = x0. Let cmax be the largest absolute value of a ci. Show that Cmax |xo| < (n + 1)
Show that single-tape TMs that cannot write on the portion of the tape containing the input string recognize only regular languages.
Show that every infinite Turing-recognizable language has an infinite decidable subset.
Show that a language is decidable iff some enumerator enumerates the language in the standard string order.
Let B = {〈M1〉, 〈M2〉, . . .} be a Turing-recognizable language consisting of TM descriptions. Show that there is a decidable language C consisting of TM descriptions such that every machine described in B has an equivalent machine in C and vice versa.
Show that the collection of Turing-recognizable languages is closed under the operation ofAa. Union.b. Concatenation.c. Star.d. Intersection.e. Homomorphism.
Show that the collection of decidable languages is closed under the operation ofAa. Union.b. Concatenation.c. Star.d. Complementation.e. Intersection.
A queue automaton is like a push-down automaton except that the stack is replaced by a queue. A queue is a tape allowing symbols to be written only on the left-hand end and read only at the right-hand end. Each write operation (we’ll call it a push) adds a symbol to the left-hand end of the queue
A Turing machine with stay put instead of left is similar to an ordinary Turing machine, but the transition function has the formδ : Q × Γ → Q × Γ × {R, S}.At each point, the machine can move its head right or let it stay in the same position. Show that this Turing machine variant is not
A Turing machine with left reset is similar to an ordinary Turing machine, but the transition function has the formδ : Q × Γ → Q × Γ × {R,RESET}.If (q, a) = (r, b,RESET), when the machine is in state q reading an a, the machine’s head jumps to the left-hand end of the tape after it
A Turing machine with doubly infinite tape is similar to an ordinary Turing machine, but 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
Say that a write-once Turing machine is a single-tape TM that can alter each tape square at most once (including the input portion of the tape). Show that this variant Turing machine model is equivalent to the ordinary Turing machine model. As a first step, consider the case whereby the Turing
Let a k-PDA be a pushdown automaton that has k stacks. Thus a 0-PDA is an NFA and a 1-PDA is a conventional PDA. You already know that 1-PDAs are more powerful (recognize a larger class of languages) than 0-PDAs.a. Show that 2-PDAs are more powerful than 1-PDAs.b. Show that 3-PDAs are not more
Give implementation-level descriptions of Turing machines that decide the following languages over the alphabet {0,1}.Aa. {w| w contains an equal number of 0s and 1s}b. {w| w contains twice as many 0s as 1s}c. {w| w does not contain twice as many 0s as 1s}
Explain why the following is not a description of a legitimate Turing machine.Mbad = “On input hpi, a polynomial over variables x1, . . . , xk:1. Try all possible settings of x1, . . . , xk to integer values.2. Evaluate p on all of these settings.3. If any of these settings evaluates to 0, accept
In Theorem 3.21, we showed that a language is Turing-recognizable iff some enumerator enumerates it. Why didn’t we use the following simpler algorithm for the forward direction of the proof? As before, s1, s2, . . . is a list of all strings in Σ*.E = “Ignore the input.1. Repeat the following
Examine the formal definition of a Turing machine to answer the following questions, and explain your reasoning.a. Can a Turing machine ever write the blank symbol on its tape?b. Can the tape alphabet ???? be the same as the input alphabet ?c. Can a Turing machine’s head ever be in the
Give a formal definition of an enumerator. Consider it to be a type of two-tape Turing machine that uses its second tape as the printer. Include a definition of the enumerated language.
Modify the proof of Theorem 3.16 to obtain Corollary 3.19, showing that a language is decidable iff some nondeterministic Turing machine decides it. (You may assume the following theorem about trees. If every node in a tree has finitely many children and every branch of the tree has finitely many
This exercise concerns TM M1, whose description and state diagram appear in Example 3.9. In each of the parts, give the sequence of configurations that M1 enters when started on the indicated input string.Aa. 11.b. 1#1.c. 1##1.d. 10#11.e. 10#10.Example 3.9 1-х, R # 0-x,R 48 xR 93 0,1-R 0,1-R 92
This exercise concerns TM M2, whose description and state diagram appear in Example 3.7. In each of the parts, give the sequence of configurations that M2 enters when started on the indicated input string.a. 0.Ab. 00.c. 000.d. 000000.Example 3.7 0→L xL 95 xR U--L xR u-R 42 93 0u,R 0-x,R u-R xR
If we disallow "-rules in CFGs, we can simplify the DK-test. In the simplified test, we only need to check that each of DK’s accept states has a single rule. Prove that a CFG without "-rules passes the simplified DK test iff it is a DCFG.
Let C = {wwR| w ∈ {0,1}*}. Prove that C is not a DCFL. Suppose that when some DPDA P is started in state q with symbol x on the top of its stack, P never pops its stack below x, no matter what input string P reads from that point on. In that case, the contents of P’s stack at that
Let B = {aibjck| i, j, k ≥ 0 and i = j or i = k}. Prove that B is not a DCFL.
Let A = L(G1) where G1 is defined in Problem 2.55. Show that A is not a DCFL.Assume that A is a DCFL and consider its DPDA P. Modify P so that its input alphabet is {a, b, c}. When it first enters an accept state, it pretends that c’s are b’s in the input from that point on. What language would
Let G1 be the following grammar that we introduced in Example 2.45. Use the DK-test to show that G1 is not a DCFG.R → S | TS → aSb | abT → aT bb | abb
Let G be the following grammar:a. Show that L(G) = {w ⊣ w contains equal numbers of a’s and b’s}. Use a proof by induction on the length of w.b. Use the DK-test to show that G is a DCFG.c. Describe a DPDA that recognizes L(G). S - TH Т— ТаТЪ | ТЪТа | € TbTa
Show that the class of DCFLs is not closed under the following operations:a. Unionb. Intersectionc. Concatenationd. Stare. Reversal
Show that every DCFG generates a prefix-free language.
Show that every DCFG is an unambiguous CFG.
We defined the CUT of language A to be CUT(A) = {yxz| xyz ∈ A}. Show that the class of CFLs is not closed under CUT.
We defined the rotational closure of language A to be RC(A) = {yx| xy ∈ A}. Show that the class of CFLs is closed under rotational closure.
Let Σ = {0,1}. Let C1 be the language of all strings that contain a 1 in their middle third. Let C2 be the language of all strings that contain two 1s in their middle third. So C1 = {xyz| x, z ∈ Σ* and y ∈ Σ*1Σ*, where |x| = |z| ≥ |y|} and C2 = {xyz| x, z ∈ Σ* and y
Let Σ = {0,1} and let B be the collection of strings that contain at least one 1 in their second half. In other words, B = {uv| u ∈ Σ*, v ∈ Σ*1 Σ* and |u| ≥ |v|}.a. Give a PDA that recognizes B.b. Give a CFG that generates B.
Consider the following CFG G:S → SS | TT → aT b | abDescribe L(G) and show that G is ambiguous. Give an unambiguous grammar H where L(H) = L(G) and sketch a proof that H is unambiguous.
Let A = {wtwR| w, t ∈ {0,1}* and |w| = |t|}. Prove that A is not a CFL.
If A and B are languages, define A ♢ B = {xy| x ∈ A and y ∈ B and |x| = |y|}.Show that if A and B are regular languages, then A ♢ B is a CFL.
For strings w and t, write w ≗ t if the symbols of w are a permutation of the symbols of t. In other words, w $ t if t and w have the same symbols in the same quantities, but possibly in a different order.For any string w, define SCRAMBLE(w) = {t| t ≗ w}. For any language A,
Let Y ={w| w=t1#t2# · · · #tk for k ≥ 0, each ti ∈ 1*, and ti ≠ tj whenever i ≠ j}.Here Σ = {1, #}. Prove that Y is not context free.
Read the definitions of NOPREFIX(A) and NOEXTEND(A) in Problem 1.40.a. Show that the class of CFLs is not closed under NOPREFIX.b. Show that the class of CFLs is not closed under NOEXTEND.Problem 1.40.Recall that string x is a prefix of string y if a string z exists where xz = y, and that x is a
Say that a language is prefix-closed if all prefixes of every string in the language are also in the language. Let C be an infinite, prefix-closed, context-free language. Show that C contains an infinite regular subset.
Refer to Problem 1.42 for the definition of the shuffle operation. Show that the class of context-free languages is not closed under shuffle.Problem 1.42For languages A and B, let the shuffle of A and B be the language{w| w = a1b1 · · · akbk, where a1 · · · ak ∈ A and b1 · · · bk ∈ B,
Refer to Problem 1.41 for the definition of the perfect shuffle operation. Show that the class of context-free languages is not closed under perfect shuffle.Problem 1.41For languages A and B, let the perfect shuffle of A and B be the language{w| w = a1b1 · · · akbk, where a1 · · · ak ∈ A
Prove the following stronger form of the pumping lemma, wherein both pieces v and y must be nonempty when the string s is broken up. If A is a context-free language, then there is a number k where, if s is any string in A of length at least k, then s may be divided into five pieces, s = uvxyz,
Give an example of a language that is not context free but that acts like a CFL in the pumping lemma. Prove that your example works. See the analogous example for regular languages in Problem 1.54.Problem 1.54.Consider the language F = {aibjck| i, j, k ≥ 0 and if i = 1 then j = k}.a. Show that F
Let G be a CFG in Chomsky normal form that contains b variables. Show that if G generates some string with a derivation having at least 2b steps, L(G) is infinite.
Consider the language B = L(G), where G is the grammar given in Exercise 2.13. The pumping lemma for context-free languages, Theorem 2.34, 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.Exercise 2.13.Let G = (V,
Show that F = {aibj | i = kj for some positive integer k} is not context free.
Let Σ = {1, 2, 3, 4} and C = {w ∈ Σ*| in w, the number of 1s equals the number of 2s, and the number of 3s equals the number of 4s}. Show that C is not context free.
Let B be the language of all palindromes over {0,1} containing equal numbers of 0s and 1s. Show that B is not context free.
Use the pumping lemma to show that the following languages are not context free.a. {0n1n0 n1n| n ≥ 0}Ab. {0n#02n#03n| n ≥ 0}Ac. {w#t| w is a substring of t, where w, t ∈ {a, b}*}d. {t1#t2# · · · #tk| k ≥ 2, each ti ∈ {a, b}*, and ti = tj for some i ≠ j}
Show that the language A in Exercise 2.9 is inherently ambiguous.Exercise 2.9Give a context-free grammar that generates the languageA = {aibjck| i = j or j = k where i, j, k ≥ 0}.Is your grammar ambiguous? Why or why not?
Give unambiguous CFGs for the following languages.a. {w| in every prefix of w the number of a’s is at least the number of b’s}b. {w| the number of a’s and the number of b’s in w are equal}c. {w| the number of a’s is at least the number of b’s in w}
Let G = (V,,R, hSTMTi) be the following grammar. G is a natural-looking grammar for a fragment of a programming language, but G is ambiguous.a. Show that G is ambiguous.b. Give a new unambiguous grammar for the same language. (STMT) → (ASSIGN) | (IF-THEN) | (IF-THEN-ELSE) (IF-THEN) if
Show that if G is a CFG in Chomsky normal form, then for any string w ∈ L(G) of length n ≥ 1, exactly 2n − 1 steps are required for any derivation of w.
For any language A, let SUFFIX(A) = {v| uv ∈ A for some string u}. Show that the class of context-free languages is closed under the SUFFIX operation.
Let E = {aibj | i ≠ j and 2i ≠ j}. Show that E is a context-free language.
LetD = {xy|x, y ∈ {0,1}* and |x| = |y| but x ≠ y}. Show thatD is a context-free language.
Let C = {x#y| x, y ∈ {0,1}* and x ≠ y}. Show that C is a context-free language.
Let Σ = {a,b}. Give a CFG generating the language of strings with twice as many a’s as b’s. Prove that your grammar is correct.
Let A/B = {w| wx ∈ A for some x ∈ B}. Show that if A is context free and B is regular, then A/B is context free.
Let CFG G be the following grammar.S → aSb | bY | Y aY → bY | aY | εGive a simple description of L(G) in English. Use that description to give a CFG for L(G), the complement of L(G).
a. Let C be a context-free language and R be a regular language. Prove that the language C \ R is context free.b. Let A = {w|w ∈ {a, b, c}* and w contains equal numbers of a’s, b’s, and c’s}. Use part (a) to show that A is not a CFL.
Use the results of Exercise 2.16 to give another proof that every regular language is context free, by showing how to convert a regular expression directly to an equivalent context-free grammar.Exercise 2.16Show that the class of context-free languages is closed under the regular operations, union,
Show that the class of context-free languages is closed under the regular operations, union, concatenation, and star.
Give a counterexample to show that the following construction fails to prove that the class of context-free languages is closed under star. Let A be a CFL that is generated by the CFG G = (V, Σ,R, S). Add the new rule S → SS and call the resulting grammar G0. This grammar is supposed to generate
Convert the following CFG into an equivalent CFG in Chomsky normal form, using the procedure given in Theorem 2.9.A → BAB | B | εB → 00 | ε
Let G = (V, Σ, R, S) be the following grammar. V = {S, T, U}; Σ = {0, #}; and R is the set of rules:S → T T | UT → 0T | T 0 | #U → 0U00 | #a. Describe L(G) in English.b. Prove that L(G) is not regular.
Convert the CFGGgiven in Exercise 2.3 to an equivalent PDA, using the procedure given in Theorem 2.20.Exercise 2.3Answer each part for the following context-free grammar G.R → XRX | SS → aT b | bT aT → XTX | X | εX → a | b

Showing 200 - 300 of 388

Introduction to the theory of computation 3rd edition Michael Sipser - Solutions

Step by Step Answers