Questions and Answers of Introduction theory computation

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
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
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
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
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
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
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.
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
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
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
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
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
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
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
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)
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
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
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
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
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.
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
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
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
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
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
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
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
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
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
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
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
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
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
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,
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
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
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,
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
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.
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
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,
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
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,
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
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 |

Showing 200 - 300 of 388