Theory of Computation problem set
CS 373 1 Theory of Computation Problem Set 1. Let β: X+ → Y. Define the Nerode machine Mβ for this β. Prove that the transition function and output function of Mβ are well defined. Is the machine reduced? If so prove it, else give a counterexample. What is the significant of the Myhill-Nerode theorem? 2. Prove that for two machines M and N, M indistinguishable from N does not imply that M has the same behavior as N. Hint: one way to prove this is to exhibit two machines, a two state machine M and a three state machine N, both over X = {0,1} and Y= {0,1} with this property. 3. Consider the machine M below. What is the input set X? What is the output set Y? What is the state set Q? Is this a Moore machine or a Mealy machine? Give the behavior βq from each state q ϵ Q, for the input sequence 32211. Give the behavior βq from each state q for the input sequence 11322. Represent machine M using a transition graph. X Q 1 2 3 q1 q2 / 0 q4 / 1 q2 / 1 q2 q3 / 0 q2 / 0 q4 / 0 q3 q2 / 1 q4 / 1 q1 / 1 q4 q3 / 1 q1 / 0 q3 / 0 MACHINE M 4. Let X = {a, b} and Y = {1, 2, none, both}. Construct a Mealy machine that outputs a 1 if the number of a’s in the input string (mod 4) is equal to 2, outputs a 2 if the number of b’s in the input string (mod 3) is equal to 1, and outputs "both" if both conditions are true. If neither condition is true it outputs "none." If such a Mealy machine does not exist indicate why not. 5. Let X = {a, b} and Y = {1, 2, none, both}. Construct a Moore machine that outputs a 1 if the input string has 1 more a's than b's or 1 less a's than b's; outputs a 2 if the input string has 2 more or 2 less a's than b's; and outputs "none" otherwise. If such a Moore machine does not exist show / prove why not. 6. Find a grammar that generates L1 ∪ L2 where L1 = { anbm : n ≥ 0, m > n } and L2 = { anb3n : n ≥ 0 }. 2 7. Let X = {a, b} and Y = {0, 1} and consider β: X+ → Y where: (a) β(x) = { 1 if the numbers of a's and b's in x are not equal, 0 otherwise. (b) β(x) = { 1 if x contains the subsequence abb and the subsequence bbab. 0 otherwise. Note that the two subsequences could overlap. For example, both the strings bbabaabba and abbab contain both subsequences. (i) For each of the two functions above, describe the Nerode equivalence classes [x]β and the functions β lx ( x ∈ X* ). (ii) For each of the two functions above, if β is not finite state realizable, prove it; if β is finite state realizable give a transition graph for the reduced machine Mβ or M(β). 8. Consider the machines A and B below. (a) Are machines A and B equivalent (A ≡ B)? Justify your answer. (b) Give the reduced machines for A and B. (c) Are machines A and B isomorphic? That is, is there a 1-1 mapping from the states of A to the states of B that preserves the state transition and output function? (d) Are the reduced machines isomorphic? X Q 1 q1 q2 / 1 q2 q2 / 0 q3 q3 / 1 q4 q3 / 1 MACHINE A X Q 1 u1 u2 / 0 u2 u2 / 0 u3 u1 / 1 u4 u4 / 1 MACHINE B