All Matches

Solution Library

Expert Answer

Textbooks

Search Textbook questions, tutors and Books

Oops, something went wrong!

Change your search query and then try again

Result Not Found

Books FREE
Tutors
Study Help
Hire a Tutor
AI Tutor New

Search
Sign In
Register

study help
computer science
introduction theory computation

Questions and Answers of Introduction theory computation

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
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
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
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
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 |
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
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
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)
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))
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
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.
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
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
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,
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
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 · ·
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
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
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
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
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 ≥
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
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 ≥
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
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
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
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
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
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
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
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
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
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|
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
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
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
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
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
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
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
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 #/
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.
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)) [
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. 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)
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
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.
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
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
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
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
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
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
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.
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
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
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
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
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
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
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
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
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
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
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
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
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. { . . .

Showing 300 - 400 of 388

1
2
3
4

Services

Sitemap
Fun
Definitions
Become Tutor
Study Help Categories
Recent Questions
Expert Questions

Company Info

Security
Copyrights
Privacy Policy
Terms & Conditions
SolutionInn Fee
Scholarship

Get In Touch

About Us
Contact Us
Career
Jobs
FAQ
Campus Ambassador

Secure Payment

Download Our App

© 2024 SolutionInn. All Rights Reserved