New Semester Started Get 50% OFF Study Help! --h --m --s Claim Now

Question Answers

Textbooks

Find textbooks, questions and answers

Oops, something went wrong!

Change your search query and then try again

Result Not Found

Books FREE
Study Help
Tutors
AI Study Planner NEW
Sell Books

Search
Sign In
Register

study help
computer science
introduction theory computation

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

Convert the CFG G4 given in Exercise 2.1 to an equivalent PDA, using the procedure given in Theorem 2.20.Exercise 2.1Recall the CFG G4 that we gave in Example 2.4. For convenience, let’s rename its variables with single letters as follows. E +T|T E → T - Tx F |F F— (E) | а
Give an informal description of a pushdown automaton that recognizes the language A in Exercise 2.9.Exercise 2.9.Give 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 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?
Show that the string the girl touches the boy with the flower has two different leftmost derivations in grammar G2 on page 103. Describe in English the two different meanings of this sentence.
Give informal English descriptions of PDAs for the languages in Exercise 2.6.Exercise 2.6.Answer each part for the following context-free grammar G.R → XRX | SS → aT b | bT aT → XTX | X | εX → a | ba. What are the variables of G?b. What are the terminals of G?c. Which is the start variable
Give context-free grammars generating the following languages.Aa. The set of strings over the alphabet {a,b} with more a’s than b’sb. The complement of the language {anbn| n ≥ 0}Ac. {w#x| wR is a substring of x for w, x ∈ {0,1}*}d. {x1#x2# · · · #xk| k ≥ 1, each xi ∈ {a,
Give informal descriptions and state diagrams of pushdown automata for the languages in Exercise 2.4.Exercise 2.4.Answer each part for the following context-free grammar G.R → XRX | SS → aT b | bT aT → XTX | X | εX → a | ba. What are the variables of G?b. What are the terminals of G?c.
Give context-free grammars that generate the following languages. In all parts, the alphabet Σ is {0,1}.Aa. {w| w contains at least three 1s}b. {w| w starts and ends with the same symbol}c. {w| the length of w is odd}Ad. {w| the length of w is odd and its middle symbol is a 0}e. {w| w = wR, that
Answer each part for the following context-free grammar G.R → XRX | SS → aT b | bT aT → XTX | X | εX → a | ba. What are the variables of G?b. What are the terminals of G?c. Which is the start variable of G?d. Give three strings in L(G).e. Give three strings not in L(G).f. True or False:
a. Use the languages A = {ambncn|m, n ≥ 0} and B = {anbncm|m, n ≥ 0} together with Example 2.36 to show that the class of context-free languages is not closed under intersection.b. Use part (a) and DeMorgan’s law (Theorem 0.20) to show that the class of context-free languages is not closed
Recall the CFG G4 that we gave in Example 2.4. For convenience, let’s rename its variables with single letters as follows.Give parse trees and derivations for each string.a. ab. a+ac. a+a+ad. ((a)) E +T|T E → T - Tx F |F F— (E) | а
Refer to Problem 1.51. Let L be a language and let X be a set of strings. Say that X is pairwise distinguishable by L if every two distinct strings in X are distinguishable by L. Define the index of L to be the maximum number of elements in any set that is pairwise distinguishable by L. The index
Let = {0,1, #}. Let C = {x#xR̅#x| x ∈ {0,1}*}. Show that C is a CFL.
Let M1 and M2 be DFAs that have k1 and k2 states, respectively, and then letU = L(M1) ∪ L(M2).a. Show that if U ≠ ⌀, then U contains some string s, where |s| < max(k1, k2).b. Show that if U ≠ Σ*, then U excludes some string s, where |s| < k1k2.
Let = {0,1}.a. Let A = {0ku0k| k ≥ 1 and u ∈ Σ*}. Show that A is regular.b. Let B = {0k1u0k| k ≥ 1 and u ∈ Σ*}. Show that B is not regular.
We define the avoids operation for languages A and B to beA avoids B = {w| w ∈ A and w doesn’t contain any string in B as a substring}.Prove that the class of regular languages is closed under the avoids operation.
Let Σ = {0,1}. Let WWk = {ww| w ∈ Σ* and w is of length k}.a. Show that for each k, no DFA can recognizeWWk with fewer than 2k states.b. Describe a much smaller NFA for W̅W̅k, the complement of WWk.
In the traditional method for cutting a deck of playing cards, the deck is arbitrarily split two parts, which are exchanged before reassembling the deck. In a more complex cut, called Scarne’s cut, the deck is broken into three parts and the middle part in placed first in the reassembly. We’ll
Let the rotational closure of language A be RC(A) = {yx| xy ∈ A}.a. Show that for any language A, we have RC(A) = RC(RC(A)).b. Show that the class of regular languages is closed under rotational closure.
A homomorphism is a function f : Σ → Γ from one alphabet to strings over another alphabet. We can extend f to operate on strings by defining f(w) = f(w1)f(w2) · · · f(wn), where w = w1w2 · · ·wn and each wi ∈ Σ. We further extend f to operate on languages by defining f(A) = {f(w)|
Prove that for each n > 0, a language Bn exists wherea. Bn is recognizable by an NFA that has n states, andb. if Bn = A1 ∪ · · · ∪ Ak, for regular languages Ai, then at least one of the Ai requires a DFA with exponentially many states.
a. Let A be an infinite regular language. Prove that A can be split into two infinite disjoint regular subsets.b. Let B and D be two languages. Write B ⋐ D if B ⊆ D and D contains infinitely many strings that are not in B. Show that if B and D are two regular languages where B b D, then we can
Let N be an NFA with k states that recognizes some language A.a. Show that if A is nonempty, A contains some string of length at most k.b. Show, by giving an example, that part (a) is not necessarily true if you replace both A’s by A̅.c. Show that if A̅ is nonempty, A̅ contains some string of
Read the informal definition of the finite state transducer given in Exercise 1.24. Prove that no FST can output wR for every input w if the input and output alphabets are {0,1}.Exercise 1.24.A finite state transducer (FST) is a type of deterministic finite automaton whose output is a string and
a. Let B = {1ky| y ∈ {0, 1}* and y contains at least k 1s, for k ≥ 1}.Show that B is a regular language.b. Let C = {1ky| y ∈ {0, 1}* and y contains at most k 1s, for k ≥ 1}.Show that C isn’t a regular language.
Let = {0,1} and letD = {w|w contains an equal number of occurrences of the substrings 01 and 10}.Thus 101 ∈ D because 101 contains a single 01 and a single 10, but 1010 ∉ D because 1010 contains two 10s and one 01. Show that D is a regular language.
Let = {1, #} and letY = {w| w = x1#x2# · · · #xk for k ≥ 0, each xi ∈ 1*, and xi ≠ xj for i ≠ j}.Prove that Y is not regular.
Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection, and complement.a. {0n1m0n| m, n ≥ 0}Ab. {0m1n| m ≠ n}c. {w| w ∈ {0,1}* is not a palindrome}8*d. {wtw| w,
Let A/B = {w| wx ∈ A for some x ∈ B}. Show that if A is regular and B is any language, then A/B is regular.
Let B and C be languages over Σ = {0, 1}. Define B C = {w∈B| for some y∈C, strings w and y contain equal numbers of 1s}.Show that the class of regular languages is closed under the operation.
Let A be any language. Define DROP-OUT(A) to be the language containing all strings that can be obtained by removing one symbol from a string in A. Thus, DROP-OUT(A) = {xz| xyz ∈ A where x, z ∈ Σ*, y ∈ Σ}. Show that the class of regular languages is closed under the
For 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, each ai, bi ∈ Σ*}.Show that the class of regular languages is closed under shuffle.
For languages A and B, let the perfect shuffle of A and B be the language{w| w = a1b1 · · · akbk, where a1 · · · ak ∈ A and b1 · · · bk ∈ B, each ai, bi ∈ Σ}.Show that the class of regular languages is closed under perfect shuffle.
Recall 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.Aa. NOPREFIX(A)
The construction in Theorem1.54 shows that everyGNFA is equivalent to aGNFA with only two states. We can show that an opposite phenomenon occurs for DFAs. Prove that for every k > 1, a language Ak ⊆ {0,1}* exists that is recognized by a DFA with k states but not by one with only k
An all-NFA M is a 5-tuple (Q,Σ, δ, q0, F) that accepts x ∈ Σ* if every possible state that M could be in after reading input x is a state from F. Note, in contrast, that an ordinary NFA accepts a string if some state among these possible states is an accept state. Prove that all-NFAs
Let Cn = {x| x is a binary number that is a multiple of n}. Show that for each n ≥ 1, the language Cn is regular.
Let Bn = {ak| k is a multiple of n}. Show that for each n ≥ 1, the language Bn is regular.
Let Σ2 be the same as in Problem 1.33. Consider the top and bottom rows to be strings of 0s and 1s, and let E = {w ∈ Σ*2| the bottom row of w is the reverse of the top row of w}. Show that E is not regular.Problem 1.33.For any string w = w1w2 · · ·wn, the reverse of w, written wR, is the
Let Σ2 be the same as in Problem 1.33. Consider each row to be a binary number and let D = {w ∈ Σ*2 | the top row of w is a larger number than is the bottom row}.For example, Show that D is regular. [HH: = D, but [:][:][H[] D
Let Here, Σ2 contains all columns of 0s and 1s of height two. A string of symbols in Σ2 gives two rows of 0s and 1s. Consider each row to be a binary number and letC = {w ∈ Σ*2| the bottom row of w is three times the top row}.For example,Show that C is regular. You may assume
LetΣ3 contains all size 3 columns of 0s and 1s. A string of symbols in Σ3 gives three rows of 0s and 1s. Consider each row to be a binary number and letB = {w ∈ Σ*3 | the bottom row of w is the sum of the top two rows}.For example,Show that B is regular. Working with BR is easier.
For any string w = w1w2 · · ·wn, the reverse of w, written wR, is the string w in reverse order, wn · · ·w2w1. For any language A, let AR = {wR| w ∈ A}. Show that if A is regular, so is AR.
Describe the error in the following “proof” that 0*1* is not a regular language. (An error must exist because 0*1* is regular.) The proof is by contradiction. Assume that 0*1* is regular. Let p be the pumping length for 0*1* given by the pumping lemma. Choose s to be the string 0p1p. You know
Use the pumping lemma to show that the following languages are not regular.Aa. A1 = {0n1n 2n| n ≥ 0}b. A2 = {www| w ∈ {a, b}*}Ac. A3 = {a2n| n ≥ 0} (Here, a2n means a string of 2n a’s.)
Convert the following regular expressions to NFAs using the procedure given in Theorem 1.54. In all parts, Σ = {a, b}.a. a(abb)* [ bb. a+ [ (ab)+c. (a [ b+)a+b+
Read the informal definition of the finite state transducer given in Exercise 1.24. Give the state diagram of an FST with the following behavior. Its input and output alphabets are {0,1}. Its output string is identical to the input string on the even positions but inverted on the odd positions. For
Using the solution you gave to Exercise 1.25, give a formal description of the machines T1 and T2 depicted in Exercise 1.24.Exercise 1.24.A finite state transducer (FST) is a type of deterministic finite automaton whose output is a string and not just accept or reject . The following are state
Read the informal definition of the finite state transducer given in Exercise 1.24. Give a formal definition of this model, following the pattern in Definition 1.5. Assume that an FST has an input alphabet Σ and an output alphabet Σ but not a set of accept states. Include a formal definition of
A finite state transducer (FST) is a type of deterministic finite automaton whose output is a string and not just accept or reject . The following are state diagrams of finite state transducers T1 and T2.Each transition of an FST is labeled with two symbols, one designating the input symbol for
Let B be any language over the alphabet Σ. Prove that B = B+ iff BB ⊆ B.
In certain programming languages, comments appear between delimiters such as /# and #/. Let C be the language of all valid delimited comment strings. A member of C must begin with /# and end with #/ but have no intervening #/. For simplicity, assume that the alphabet for C is Σ = {a, b, /, #}.a.
Use the procedure described in Lemma 1.60 to convert the following finite automata to regular expressions. a a 1 а,b 1 b a b a 3 (а) (b)
For each of the following languages, give two strings that are members and two strings that are not members—a total of four strings for each part. Assume the alphabet Σ = {a,b} in all parts.a. a*b*b. a(ba) *bc. a* ∪ b*d. (aaa)*e. Σ*aΣ*bΣ*aΣ*f. aba ∪ babg.
Use the procedure described in Lemma 1.55 to convert the following regular expressions to nondeterministic finite automata.a. (0 ∪ 1)*000(0 ∪ 1)*b. (((00)* (11)) [ 01) *c. ∅*
Give regular expressions generating the languages of Exercise 1.6.Exercise 1.6Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is {0,1}.a. {w| w begins with a 1 and ends with a 0}b. {w| w contains at least three 1s}c. {w| w contains the substring 0101
a. Give an NFA recognizing the language (01 ∪ 001 ∪ 010)*.b. Convert this NFA to an equivalent DFA. Give only the portion of the DFA that is reachable from the start state.
Use the construction given in Theorem 1.39 to convert the following two nondeterministic finite automata to equivalent deterministic finite automata. a 1 1 2 a a,b a а,b 2 (а) (b) 3. (6)
Give a counterexample to show that the following construction fails to prove Theorem 1.49, the closure of the class of regular languages under the star operation.7 Let N1 = (Q1,Σ, δ, q1, F1) recognize A1. Construct N = (Q1, Σ, δ1, q1, F1) as follows. N is supposed to recognize A*1 .a. The
a. Show that if M is a DFA that recognizes language B, swapping the accept and nonaccept states inM yields a new DFA recognizing the complement of B. Conclude that the class of regular languages is closed under complement.b. Show by giving an example that if M is an NFA that recognizes language C,
Let F be the language of all strings over {0,1} that do not contain a pair of 1s that are separated by an odd number of symbols. Give the state diagram of a DFA with five states that recognizes F. (You may find it helpful first to find a 4-state NFA for the complement of F.)
Let D = {w| w contains an even number of a’s and an odd number of b’s and does not contain the substring ab}. Give a DFA with five states that recognizes D and a regular expression that generates D. (Suggestion: Describe D more simply.)
Prove that everyNFA can be converted to an equivalent one that has a single accept state.
Use the construction in the proof of Theorem 1.49 to give the state diagrams of NFAs recognizing the star of the languages described ina. Exercise 1.6b.b. Exercise 1.6j.c. Exercise 1.6m.Exercise 1.6b. {w| w contains at least three 1s}j. {w| w contains at least two 0s and at most one 1}m. The empty
Use the construction in the proof of Theorem 1.47 to give the state diagrams of NFAs recognizing the concatenation of the languages described ina. Exercises 1.6g and 1.6i.b. Exercises 1.6b and 1.6m.Exercises 1.6b. {w| w contains at least three 1s}g. {w| the length of w is at most 5}i. {w| every odd
Use the construction in the proof of Theorem 1.45 to give the state diagrams of NFAs recognizing the union of the languages described ina. Exercises 1.6a and 1.6b.b. Exercises 1.6c and 1.6f.Exercises 1.6a. {w| w begins with a 1 and ends with a 0}b. {w| w contains at least three 1s}c. {w| w contains
Give state diagrams of NFAs with the specified number of states recognizing each of the following languages. In all parts, the alphabet is {0,1}.Aa. The language {w| w ends with 00} with three statesb. The language of Exercise 1.6c with five statesc. The language of Exercise 1.6l with six statesd.
Give state diagrams of DFAs recognizing the following languages. In all parts, the alphabet is {0,1}.a. {w| w begins with a 1 and ends with a 0}b. {w| w contains at least three 1s}c. {w| w contains the substring 0101 (i.e., w = x0101y for some x and y)}d. {w| w has length at least 3 and its third
Each of the following languages is the complement of a simpler language. In each part, construct a DFA for the simpler language, then use it to give the state diagram of a DFA for the language given. In all parts, Σ = {a, b}.Aa. {w| w does not contain the substring ab}Ab. {w| w does not contain
Each of the following languages is the intersection of two simpler languages. In each part, construct DFAs for the simpler languages, then combine them using the construction discussed in footnote 3 (page 46) to give the state diagram of a DFA for the language given. In all parts, Σ = {a, b}.a.
The formal description of a DFA M is [{q1, q2, q3, q4, q5}, {u, d}, δ, q3, {q3}], where δ is given by the following table. Give the state diagram of this machine. u d 91 92 q2 93 92 q4 93 45 95 94
Give the formal description of the machines M1 and M2 pictured in Exercise 1.1.Exercise 1.1The following are the state diagrams of two DFAs,M1 andM2. Answer the following questions about each of these machines. a a 42 a 92 a a, b 93 b 13 Ja 94 a M1 M2
The following are the state diagrams of two DFAs,M1 andM2. Answer the following questions about each of these machines.a. What is the start state?b. What is the set of accept states?c. What sequence of states does the machine go through on input aabb?d. Does the machine accept the string aabb?e.
Use Theorem 0.25 to derive a formula for calculating the size of the monthly payment for amortgage in terms of the principal P, the interest rate I, and the number of payments t. Assume that after t payments have been made, the loan amount is reduced to 0. Use the formula to calculate the dollar
Ramsey’s theorem. Let G be a graph. A clique in G is a subgraph in which every two nodes are connected by an edge. An anti-clique, also called an independent set, is a subgraph in which every two nodes are not connected by an edge. Show that every graph with n nodes contains either a clique or an
Show that every graph with two or more nodes contains two nodes that have equal degrees.
Find the error in the following proof that all horses are the same color. CLAIM: In any set of h horses, all horses are the same color. PROOF: By induction on h.Basis: For h = 1. In any set containing just one horse, all horses clearly are the same color.Induction step: For k ≥ 1,
Let S(n) = 1 + 2 + · · · + n be the sum of the first n natural numbers and let C(n) = 13 + 23 + · · · + n3 be the sum of the first n cubes. Prove the following equalities by induction on n, to arrive at the curious conclusion that C(n) = S2(n) for every n.a. S(n) = 1/2n(n + 1).b. C(n) = 1/4
Find the error in the following proof that 2 = 1. Consider the equation a = b. Multiply both sides by a to obtain a2 = ab. Subtract b2 from both sides to get a2 − b2 = ab − b2. Now factor each side, (a + b)(a − b) = b(a − b), and divide each side by (a − b) to get a + b = b.
Write a formal description of the following graph. 1 4 2 3 6
Consider the undirected graph G = (V,E) where V , the set of nodes, is {1, 2, 3, 4} and E, the set of edges, is {{1, 2}, {2, 3}, {1, 3}, {2, 4}, {1, 4}}. Draw the graph G. What are the degrees of each node? Indicate a path from node 3 to node 4 on your drawing of G.
For each part, give a relation that satisfies the condition.a. Reflexive and symmetric but not transitiveb. Reflexive and transitive but not symmetricc. Symmetric and transitive but not reflexive
Let X be the set {1, 2, 3, 4, 5} and Y be the set {6, 7, 8, 9, 10}. The unary function f : X → Y and the binary function g : X → Y −Y are described in the following tables.a. What is the value of f(2)?b. What are the range and domain of f?c. What is the value of g(2, 10)?d. What are the range
If C is a set with c elements, how many elements are in the power set of C? Explain your answer.
If A has α elements and B has b elements, how many elements are in A × B? Explain your answer.
Let A be the set {x, y, z} and B be the set {x, y}.a. Is A a subset of B?b. Is B a subset of A?c. What is A ∪ B?d. What is A ⋂ B?e. What is A × B?f. What is the power set of B?
Write formal descriptions of the following sets.a. The set containing the numbers 1, 10, and 100b. The set containing all integers that are greater than 5c. The set containing all natural numbers that are less than 5d. The set containing the string abae. The set containing the empty stringf. The
Examine the following formal descriptions of sets so that you understand whichmembers they contain. Write a short informal English description of each set.a. {1, 3, 5, 7, . . . }b. { . . . ,−4,−2, 0, 2, 4, . . . }c. {n| n = 2m for some m in N}d. {n| n = 2m for some m in N, and n = 3k for some k

Showing 300 - 400 of 388

1
2
3
4

Step by Step Answers

Services

Sitemap
Fun
Definitions
Become Tutor
Used Textbooks
Study Help Categories
Recent Questions
Expert Questions
Campus Wear
Sell Your Books

Company Info

Security
Copyrights
Privacy Policy
Terms & Conditions
SolutionInn Fee
Scholarship
Online Quiz
Give Feedback, Get Rewards

Get In Touch

About Us
Contact Us
Career
Jobs
FAQ
Student Discount
Campus Ambassador

Secure Payment

Download Our App

© 2026 SolutionInn. All Rights Reserved