Introduction To Computer Theory 2nd Edition Daniel I. A. Cohen - Solutions

Find CFGs that generate these regular languages over the alphabet Σ = {a b}:(i) The language defined by (aaa + b)*.(ii) The language defined by (a + b)*(bbb + aaa)(a + b)*.(iii) All strings without the substring aaa.(iv) All strings that end in b and
Invent a form of prefix notation for the system of propositional calculus used in this chapter that enables us to write all well-formed formulas without the need for parentheses (and without ambiguity).
Consider the CFGProve that this generates the language of all strings with a triple b in them, which is the language defined by(a + b)*bbb(a + b)* S→XYX X→ax|bx|A Y→bbb
Show that the following CFGs that use A are ambiguous:(i) S → XaXX → aX l bX I Λ(ii) S → aSX I ΛX → aX l a(iii) S → aS l bS l aaS I Λ(iv) Find unambiguous CFGs that generate these three languages.(v) For each of these three languages, find an unambiguous grammar that generates exactly
Consider the CFG(i) Prove that X can generate any b*.(ii) Prove that XaXaX can generate any b*ab*ab*.(iii) Prove that S can generate (b*ab*ab*)*.(iv) Prove that the language of this CFG is the set of all words in (a + b)* with an even number of a's with the following exception: We
(i) In response to "Time flies like an arrow," the tout said, "My watch must be broken."How many possible interpretations of this reply are there?(ii) Chomsky found three different interpretations for "I had a book stolen." Explain them. Are their parsing trees different?
(i) Consider the CFGWhat is the language this CFG generates?(ii) Consider the CFGWhat is the language this CFG generates? S→ aX V|X9|XD-X
Find CFGs for the following languages over the alphabet Σ = {a b}:(i) All words in which the letter b is never tripled.(ii) All words that have exactly two or three b's.(iii) All words that do not have the substring ab.(iv) All words that do not have the substring baa.(v) All words that have
(i) Consider the CFG for "some English" given in this chapter. Show how these productions can generate the sentenceItchy the bear hugs jumpy the dog.(ii) Change the productions so that an article cannot come between an adjective and its noun.(iii) Show how in the CFG for "some English" we can
Consider the CFGS → aS |bbProve that this generates the language defined by the regular expressiona*bb
Given two regular expressions r1 and r2, construct a decision procedure to determine whether the language of r1 is contained in the language of r2.
(i) Construct a decision procedure to determine whether a given FA accepts at least one word that contains the letter b.(ii) Construct a decision procedure to determine whether a given FA accepts some words of even length.
By using blue paint, determine which of the following FAs accept any words: (1 b (1 b
By moving the start state, construct a decision procedure to determine whether a given FA accepts at least one word that starts with an a.
Consider the following simplified algorithm to decide whether an FA with exactly N states has an empty language:Step 1 Take the edges coming out of each final state and tum them into loops going back to the state they started from.Step 2 Relabel all edges with the letter x. (We now have an
Without converting it into a regular expression or an FA, give an algorithm that decides whether the language of an NFA is empty, finite, or infinite.
Without converting it into a regular expression or an FA, give an algorithm that decides whether a TG accepts any words.
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:L1 L2(ab*)* a(a + b)*
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:L1 L2(i) Even-length strings
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:L1 L2(ab*)* b(a + b)*
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:L1 L2(b + ab)*(a + Λ) (b + ab*a)*ab*
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:L1 L2(b + ab)*(a + Λ) (a + ba)*a
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:L1 L2(b + ab)*(a + Λ) (a + b)*aa(a + b)*
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:L1 L2(a + b)b(a + b)* (a + b)*b
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:L1 L2(a + b)b(a + b)* (a + b)*aa(a + b)*
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:L1 L2(a + b)b(a + b)* b(a + b)*
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:L1 L2(a + b)*a (a + b)*b
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:L1 L2(a + b)*a (a + b)*aa(a + b)*
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:L1 L2Odd-length strings a(a + b)*
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:L1 L2Even-length strings EVEN-EVEN
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:L1 L2Even-length strings (b + ab)*(a + Λ)
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:L1 L2Even-length strings (a + b)*aa(a + b)*
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:L1 L2All strings of
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:L1 L2(ab*)* (a + b)*aa(a + b)*
For let (Me)2 mean that given a Mealy machine, an input string is processed and then the output string is immediately fed into the machine (as input) and reprocessed. Only this second resultant output is considered the final output of (Me)2. If the final output string is the same as the original
For let (Me)2 mean that given a Mealy machine, an input string is processed and then the output string is immediately fed into the machine (as input) and reprocessed. Only this second resultant output is considered the final output of (Me)2. If the final output string is the same as the original
For similarly, given two Mealy machines, let (Me1)(Me2) mean that an input string is processed on Me1 and then the output string is immediately fed into Me2 (as input) and reprocessed. Only this second resultant output is considered the final output of (Me1)(Me2). If the final output string is the
For similarly, given two Mealy machines, let (Me1)(Me2) mean that an input string is processed on Me1 and then the output string is immediately fed into Me2 (as input) and reprocessed. Only this second resultant output is considered the final output of (Me1)(Me2). If the final output string is the
You are given these two Mealy machines:Notice that they are indeed different and show that each is the inverse machine of the other, that means that (Me1)(Me2) = identity = (Me2)(Me1) M₁ 0/1 1/0 0/0, 1/1 1/0, 0/1 M2 0/1 1/0 0/1, 1/0 0/0, 1/1
Prove that there is no Mealy machine that reverses an input string, that is, Me(s) = transpose(s).
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:L1 L2(a + b)*a b(a + b)*
(i) Design a machine to perform a parity check on the input string; that is, the output string ends in 1 if the total number of 1-bits in the input string is odd and 0 if the total number of 1-bits in the input string is even (the front part of the output string is ignored).(ii) In your answer to
Given a bit string of length n, the shift-left-cyclic operation places the first bit at the end, leaving the rest of the bits unchanged. For example, SLC (100110) = 001101.(i) Build a Mealy machine with input and output alphabet {0 1 $} such that for any bit string x when we input the n + 1 bits
For let (Me)2 mean that given a Mealy machine, an input string is processed and then the output string is immediately fed into the machine (as input) and reprocessed. Only this second resultant output is considered the final output of (Me)2. If the final output string is the same as the original
For each of the following Moore machines, construct the transition and output tables:(i)(ii)(iii)(iv)(v) 40/0 a b a. b 91/1
Suppose we define a Less machine to be a Moore machine that does not automatically print the character of the start state. The first character it prints is the character of the second state it enters. From then on, for every state it enters it prints a character, even when it reenters the start
Mealy machines can also be defined by transition tables. The rows and the columns are both labeled with the names of the states. The entry in the table is the label of the edge (or edges) going from the row state to the column state (if there is no such edge, this entry is blank).Construct the
Draw a Mealy machine equivalent to the following sequential circuit: input OR A OR DELAY B AND out put
Build an FA that accepts only those words that begin or end with a double letter.
(i) Build an FA that accepts only those words that have more than four letters.(ii) Build an FA that accepts only those words that have fewer than four letters.(iii) Build an FA that accepts only those words with exactly four letters.
For construct a regular expression defining each of the following languages over the alphabet Σ = {a b}:(i) All strings that end in a double letter.(ii) All strings that do not end in a double letter.
For construct a regular expression defining each of the following languages over the alphabet Σ = {a b}:All words that contain at least one of the strings s1, s2, s3, or s4.
Show that if n is less than 31, then xn can be shown to be in POLYNOMIAL in fewer than eight steps.
(i) If S = {a b} and T* = S*. prove that T must contain S.(ii) Find another pair of sets S and T such that if T* = S*. then S ⊂ T.
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:L1 L2(i) Even-length strings
For each of the following pairs of regular languages, find a regular expression and an FA that each define L1 ∩ L2:We have seen that because the regular languages are closed under union and complement, they must be closed under intersection. Find a collection of languages that is closed under
For show by the method described in this chapter that the following pairs of FAs are equivalent: FA₁ b (1 FA₂ b +
Use the pumping lemma to show that each of these languages is nonregular:(i) {anbn+1} = {abb aabbb aaabbbb . . .}(ii) {anbnan} = {aba aabbaa aaabbbaaa aaaabbbbaaaa . . .}(iii) {anb2n} = {abb aabbbb aaabbbbbb . . .}(iv) {anban} = {aba aabaa aaabaaa . . .}(v) {anbnam where n = 0, 1 , 2, . . . and m =
For show by the method described in this chapter that the following pairs of FAs are equivalent: FA +1 (1 (1 a. b FA₂ a b
For show by the method described in this chapter that the following pairs of FAs are equivalent: FA₁ +: 5 b + a FA₂ a. b
For show by the method described in this chapter that the following pairs of FAs are equivalent:Why is this problem wrong? How can it be fixed? FA₁ +1 [] a b FA2 (1 8 –
Using the method of intersecting each machine with the complement of the other, show thatdo not accept the same language. (1 (1 8. and (1 (1 h (1 + "
Using the method of intersecting each machine with the complement of the other, show thatdo not accept the same language. FA₁ a a X'3+ .X₂ + b and FA₂ M ± (1 (1 (1
List the 56 strings that will suffice to test whether a three state FA over Σ = {a b} has a finite language.
By using blue paint, determine which of the following FAs accept any words: a. b (1 a. h h
By using blue paint, determine which of the following FAs accept any words: b a. b h (1 (1
By using blue paint, determine which of the following FAs accept any words: (1 a a. b
(i) Based on the table representation for Moore machines, how many different Mo's are there with four states?(ii) How many different Moore machines are there with n states?
For construct a regular expression defining each of the following languages over the alphabet Σ = {a b} :(i) All words that do not have the substring ab.(ii) All words that do not have both the substrings bba and abb.
Consider the language S*, where S = {a b} .How many words does this language have of length 2? of length 3 ? of length n?
(i) Let S = {ab bb} and let T = {ab bb bbbb}. Show that S* = T*.(ii) Let S = {ab bb} and let T = {ab bb bbb}. Show that S* ≠ T* , but that S* ⊂ T*.(iii) What principle does this illustrate?
Let S = {a bb bab abaab}. Is abbabaabab in S*? Is abaabbabbaabb? Does any word in S* have an odd total n umber of b's?
Let us define(S**)* = S***Is this set bigger than S*? Is it bigger than S?
(i) Consider the language S*, where S = {aa ab ba bb}. Give another description of this language.(ii) Give an example of a set S such that S* only contains all possible strings of a's and b's that have length divisible by 3.(iii) Let S b e all strings o f a's and b's with odd length. What is
(i) Write out the full recursive definition for the propositional calculus that contains the symbols V and /\ as well as ⇁ and →.(ii) What are all the forbidden substrings of length 2 in this language?
(i) Give a recursive definition for the set ODD = {1 3 5 7 . . . }.(ii) Give a recursive definition for the set of strings of digits 0, 1, 2 , 3, . . . 9 that cannot start with the digit 0.
In this chapter, we attempted to define the positive numbers by the follow i ng rules :Rule 1 1 is in L.Rule 2 If x and y are in L, then so are x + y, x*y, and x/y.The language L defined in this way is a famous mathematical set. What is it? Prove it.
Give two recursive definitions for the setPOWERS-OF-TWO = {1 2 4 8 16 . . . }Use one of them to prove that the product of two POWERS-OF-TWO is also a POWER-OF-TWO.
For construct a regular expression defining each of the following languages over the alphabet Σ = {a b} :All words in which a appears tripled, if at all. This means that every clump of a's contains 3 or 6 or 9 or 1 2 . . . a's.
For construct a regular expression defining each of the following languages over the alphabet Σ = {a b} :All words that contain exactly two b's or exactly three b's, not more.
For construct a regular expression defining each of the following languages over the alphabet Σ = {a b} :All strings that have exactly one double letter in them.
For construct a regular expression defining each of the following languages over the alphabet Σ = {a b} :All words in which a is tripled or b is tripled, but not both. This means each word contains the substring aaa or the substring bbb but not both.
For construct a regular expression defining each of the following languages over the alphabet Σ = {a b} :All strings in which the total number of a's is divisible by 3 no matter how they are distributed, such as aabaabbaba.
For construct a regular expression defining each of the following languages over the alphabet Σ = {a b} :(i) All strings in which any h's that occur are found in clumps of an odd number at a time, such as abaabbbab.(ii) All strings that have an even number of a's and an odd number of h's.(iii) All
For show that the following pairs of regular expressions define the same language over the alphabet Σ = {a b} :(i) (ab)*a and a(ba)*(ii) (a* + b)* and (a + b)*(iii) (a* + b*)* and (a + b)*
For show that the following pairs of regular expressions define the same language over the alphabet Σ = {a b} :(i) Λ* and Λ(ii) (a* b)*a* and a*(ba*)*(iii) (a*bbb)*a* and a*(bbba*)*
For show that the following pairs of regular expressions define the same language over the alphabet Σ = {a b} :(i) ((a + bb)*aa)* and Λ + (a + bb)*aa(ii) (aa)*(A + a) and a*(iii) a(aa)*(A + a)b + b and
(D. N. Arden) Let R, S, and T be three languages and assume that Λ is not in S. Prove the following statements:(i) From the premise that R = SR + T, we can conclude that R = S*T.(ii) From the premise that R = S*T, we can conclude that R = SR + T.
Build an FA that accepts only the words baa, ab, and abb and no other strings longer or shorter.
For each of the next 10 words, decide which of the six machines on the next page accept the given word.(i) Λ(ii) a(iii) b(iv) aa(v) ab(vi) aba(vii) abba(viii) bab(ix) baab(x) abbb TG " tah.h TG. TG aub. bat are h h . h " tah wi TG₁ TG₁ (1 TGB تو ہیں ہی
(i) Build an FA with three states that accepts all strings.(ii) Show that given any FA with three states and three + 's, it accepts all input strings.(iii) If an FA has three states and only one +, must it reject some inputs?
Build an FA that accepts only those words that do not end with ba.
Build an FA that accepts only those words that have an even number of substrings ab.
(i) Build an FA that accepts the language of all strings of a's and h's such that the next-to-last letter is an a.(ii) Build an FA that accepts the language of all strings of length 4 or more such that the next-to-last letter is equal to the second letter of the input string.
Build a machine that accepts all strings that have an even length that is not divisible by 6.
Show that any language that can be accepted by a TG can be accepted by a TG with an even number of states.
How many different TGs are there over the alphabet {a b} that have two states?
Prove that for every TG there is another TG that accepts the same language but has only one + state.
Build a TG that accepts the language L1 of all words that begin and end with the same double letter, either of the form aa . . . aa or bb . . . bb.
If OURSPONSOR is a language that is accepted by a TG called Henry, prove that there is a TG that accepts the language of all strings of a's and b's that end in a word from OURSPONSOR.

Showing 100 - 200 of 244

Introduction To Computer Theory 2nd Edition Daniel I. A. Cohen - Solutions

Step by Step Answers