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

(i) Suppose that L is a finite language whose words are w1 , w2 , w3 , • • • , w83 . Prove that there is a TG that accepts exactly the language L.(ii) Of all TGs that accept exactly the language L, what is the one with the fewest number of states?
Given a TG, called TG1 , that accepts the language L1 and a TG, called TG2, that accepts the language L2, show how to build a new TG (called TG3) that accepts exactly the language L1 + L2.
Given a TG for some arbitrary language L, what language would it accept if every + state were to be connected back to every - state by Λ-edges? For example, by this method, I bb ba b ab a becomes bb ba .1 ab
(i) Let the language L be accepted by the transition graph T and let L not contain the word Λ. Show how to build a new TG that accepts exactly all the words in L and the word Λ.(ii) Given TG1 that accepts the language L1, show how to build a TG that accepts the language L*.
An FA with four states was sitting unguarded one night when vandals came and stole an edge labeled a. What resulted was a TG that accepted exactly the language b* . In the morning the FA was repaired, but the next night vandals stole an edge labeled h and what resulted was a TG that accepted a*.
Let the language L be accepted by the transition graph T and let L not contain the word ba. We want to build a new TG that accepts exactly L and the word ba.(i) One suggestion is to draw an edge from - to + and label it ba. Show that this does not always work.(ii) Another suggestion is to draw a
Let L be any language. Let us define the transpose of L to be the language of exactly those words that are the words in L spelled backward. If w El, then reverse(w) El. For example, ifL = {a abb bbaab bbbaa}thentranspose(L) = {a bba baabb aabbb}(i) Prove that if there is an FA that accepts L, then
Transition graph T accepts language L. Show that if L has a word of odd length, then T has an edge with a label with an odd number of letters.
A student walks into a classroom and sees on the blackboard a diagram of a TG with two states that accepts only the word Λ. The student reverses the direction of exactly one edge, leaving all other edges and all labels and all + 's and - 's the same. But now the new TG accepts the language a*.
Let us now consider an algorithm for determining whether a specific TG that has no Λ-edges accepts a given word:Step 1 Number each edge in the TG in any order with the integers 1, 2, 3, . . . , x, where x is the number of edges in the TG.Step 2 Observe that if the word has y letters and is
Each of the following is a Moore machine with alphabet Σ = {a b} and output alphabet Γ = {0 1} . Given the transition and output tables, draw the machines.(i)(ii)(iii)(iv)(v) a 90 91 91 9₁ 92 91 b 92 91 90 Output 1 0 1
Give recursive definitions for the following languages over the alphabet {a b}:(i) The language EVENSTRING of all words of even length.(ii) The language ODDSTRING of all words of odd length.(iii) The language AA of all words containing the substring aa.(iv) The language NOTAA of all words not
(i) Consider the following recursive definition of 3-PERMUTATION:Rule 1 123 is a 3-PERMUTATION.Rule 2 If xyz is a 3-PERMUTATION, then so are zyx and yzx.Show that there are six different 3-PERMUTATIONs.(ii) Consider the following recursive definition of 4-PERMUTATION:Rule 1 1234 is a
(i) Let us reconsider the regular expression(a + b)*a(a + b)*b(a + b)*Show that this is equivalent to(a + b)*ab(a + b)*In the sense that they define the same language.(ii) Show
Describe (in English phrases) the languages associated with the following regular expressions:(i) (a + b)*a(Λ + bbbb)(ii) (a(a + bb)*)*(iii) (a(aa)*b(bb)*)*(iv) (b(bb)*)*(a(aa)*b(bb)*)*(v) (b(bb)*)*(a(aa)*b(bb )*)*(a(aa)*)*(vi) ((a + b)a)*
(i) Explain why we can take any pair of equivalent regular expressions and replace the letter a in both with any regular expression R and the letter b with any regular expression S and the resulting regular expressions will have the same language. For example, 16(ii), which
Consider all the possible FAs over the alphabet {a b} that have exactly two states. An FA must have a designated start state, but there are four possible ways to place the + 's:Each FA needs four edges (two from each state), each of which can lead to either of the states. There are 24 = 16 ways to
Show that there are exactly 5832 different finite automata with three states. x, y, z over the alphabet {a b}, where x is always the start state.
Suppose a particular FA, called FIN, has the property that it had only one final state that was not the start state. During the night, vandals come and switch the + sign with the - sign and reverse the direction of all the edges.(i) Show that the picture that results might not actually be an FA at
We define a removable state as a state such that if we erase the state itself and the edges that come out of it, what results is a perfectly good-looking FA.(i) Give an example of an FA that contains a removable state.(ii) Show that if we erase a removable state the language defined by the reduced
Build an FA such that when the labels a and b are swapped the new machine is different from the old one but equivalent (the language defined by these machines is the same).
Describe in English the languages accepted by the following FAs:(i)(ii)(iii)(iv) Write regular expressions for the languages accepted by these three machines. a, b a a, b
The following is an FA over the alphabet Σ = {a b c}. Prove that it accepts all strings that have an odd number of occurrences of the substring abc. b, c 6+ a b a 2 b b 5+ a a b 3 C 4 + b. c
Consider the following FA:(i) Show that any input string with more than three letters is not accepted by this FA.(ii) Show that the only words accepted are a, aab, and bab.(iii) Show that by changing the location of + signs alone, we can make th is FA accept the language {bb aba bba} .(iv) Show
Let us consider the possibility of an infinite automaton that starts with this infinite binary tree:Let L be any infinite language of strings of a's and h's whatsoever. Show that by the judicious placement of + 's, we can tum the picture above into an infinite automaton to accept the language L.
Consider the language S*, where S = {ab ba}. Write out all the words in S* that have seven or fewer letters. Can any word in this language contain the substrings aaa or bbb? What is the smallest word that is not in this language?
Consider the language S*, where S = {a ab ba} . Is the string (abbba) a word in this language? Write out all the words in this language with six or fewer letters. What is another way in which to describe the words in this language? Be careful , this is not simply the language of all words without
Consider the language S*, where S = {aa aba baa} . Show that the words aabaa, baaabaaa, and baaaaababaaaa are all in this language. Can any word in this language be interpreted as a string of elements from S in two different ways? Can any word in this language have an odd total number of a's?
Consider the language S*, where S = {xx xxx}. In how many ways can x19 be written as the product of words in S? This means: How many different factorizations are there of x19 into xx and xxx?
Consider the language PALINDROME over the alphabet {a b}.(i) Prove that if x is in PALINDROME, then so is xn for any n.(ii) Prove that if y3 is in PALINDROME, then so is y.(iii) Prove that if zn is in PALINDROME for some n (greater than 0), then z itself is also.(iv) Prove that PALINDROME has as
Show that if the concatenation of two words (neither A) in PALIN DROME is also a word in PALINDROME, then both words are powers of some other word; that is, if x and y and xy are al l in PALINDROME, then there is a word z such that x = zn| and y = zm for some integers n and m (maybe n or m = 1).
Prove that for all sets S,(i) (S+)* = (S*)*(ii) (S+)+ = S+(iii) Is (S*)+ = (S+)* for all sets S?
Suppose that for some language L we can always concatenate two words in L and get another word in L if and only if the words are not the same. That is, for any words w1 and w2 in L where w1 ≠ w2, the word w1 w2 is in L but the word w1 w1 is not in L. Prove that this cannot happen.
Let w be a string o f letters and let the language T be defined as adding w to the language S. Suppose further that T* = S*.(i) Is it necessarily true that w ∈ S?(ii) Is it necessarily true that w ∈ S*?
One student suggested the following algorithm to test a string of a's and b's to see if it is a word in S*. where S = {aa ba aba abaab}. Step 1, cross off the longest set of characters from the front of the string that is a word in S. Step 2, repeat step 1 until it is no longer possible. If what
A language L1 is smaller than another language L2 if L1 ⊂ L2 and L1 ≠ L2• Let T be any language closed under concatenation; that is, if t1 ∈ T and t2 ∈ T. then t1 t2 is also an element of T. Show that if T contains S but T ≠ S*, then S* is smaller than T. We can summarize this by saying
Using the second recursive definition of the set EVEN, how many different ways can we prove that 14 is in EVEN?
Using the second recursive definition of EVEN, what is the smallest number of steps required to prove that 100 is EVEN? Describe a good method for showing that 2n is in EVEN.
Show that the following is another recursive definition of the set EVEN :Rule 1 2 and 4 are in EVEN.Rule 2 If x is in EVEN, then so is x + 4.
Using any recursive definition of the set EVEN, show that all the numbers in it end in the digits 0, 2, 4, 6, or 8.
The set POLYNOMIAL defined in this chapter contains only the polynomials in the one variable x. Write a recursive definition for the set of all polynomials in the two variables x and y.
Are there any substrings of length 3 that cannot occur that do not contain forbidden substrings of length 2? (This means that /// is already known to be illegal because it contains the forbidden substring //.) What is the longest forbidden substring that does not contain a shorter forbidden
The rules given earlier for the set AE allow for the peculiar expressions (((((9))))) and - ( - ( - ( - (9)))) It is not really harmful to allow these in AE, but is there some modified definition of AE that eliminates this problem?
(i) When asked to give a recursive definition for the language PA LINDROM E over the alphabet Σ = {a b}, a student wrote:Rule 1 a and b are in PALINDROME.Rule 2 If x is in PALINDROME, then so are axa and bxb.Unfortunately, all the words in the language defined above have an odd length and so it is

Showing 200 - 300 of 244

1
2
3

Step by Step Answers