CS 341 Homework 4Deterministic Finite Automata1. If M is a deterministic finite automaton. Under exactly what circumstances is L(M)?2. Describe informally the languages accepted by each of the following deterministic FSMs: (from Elements of the Theory of Computation, H. R. Lewis and C. H. Papdimitriou, Prentice-Hall, 1998.)Homework 4 Deterministic Finite Automata 13. Construct a deterministic FSM to accept each of the following languages: (a) {w {a, b}* : each ‘a’ in w is immediately preceded and followed by a ‘b’} (b) {w {a, b}* : w has abab as a substring} (c) {w {a, b}* : w has neither aa nor bb as a substring} (d) {w {a, b}* : w has an odd number of a's and an even number of b's} (e) {w {a, b}* : w has both ab and ba as substrings}4. Construct a deterministic finite state transducer over {a, b} for each of the following tasks: (a) On input w produce an, where n is the number of occurrences of the substring ab in w. (b) On input w produce an, where n is the number of occurrences of the substring aba in w. (c) On input w produce a string of length w whose ith symbol is an a if i = 1 or if i > 1 and the ith and (i-1)st symbols of w are different; otherwise, the ith symbol of the output is b.5. Construct a dfa accepting L = {w {a, b}* : w contains no occurrence of the string ab}.6. What language is accepted by the following fsa? b 1 b 2 a 3 a a b a a4 b 5 6 a,b7. Give a dfa accepting {x {a, b}* : at least one a in x is not immediately followed by b}.8. Let L = {w {a, b}* : w does not end in ba}. (a) Construct a dfa accepting L. (b) Give a regular expression for L.9. Consider L = {anbn : 0 n 4} (a) Show that L is regular by giving a dfa that accepts it. (b) Give a regular expression for L.10. Construct a deterministic finite state machine to accept strings that correspond to odd integers without leading zeros.11. Imagine a traffic light. Let = {a}. In other words, the input consists just of a string of a's. Think of each a as the output from a timer that signals the light to change. Construct a deterministic finite state transducer whose outputs are drawn from the set {Y, G, R} (corresponding to the colors yellow, green, and red). The outputs of the transducer should correspond to the standard traffic light behavior.12. Recall the finite state machine that we constructed in class to accept $1.00 in change or bills. Modify the soda machine so that it actually does something (i.e., some soda comes out) by converting our finite state acceptor to a finite state transducer. Let there be two buttons, one for Coke at $.50 and one for Water at $.75 (yes, it's strange that water costs more than Coke. The world is a strange place). In any case, there will now be two new symbols in the input alphabet, C and W. The machine should behave as follows: The machine should keep track of how much money has been inserted. If it ever gets more than $1.50, it should spit back enough to get it under $1.00 but keep it above $.75.Homework 4 Deterministic Finite Automata 2 If the Coke or Water button is pushed and enough money has been inserted, the product and the change should be output. If a button is pushed and there is not enough money, the machine should remember the button push and wait until there is enough money, at which point it should output the product and the change.13. Consider the problem of designing an annoying buzzer that goes off whenever you try to drive your car andyou're not wearing a seat belt. (For simplicity, we'll just worry about the driver's possible death wish. If you want to make this harder, you can worry about the other seats as well.) Design a finite state transducer whose inputs are drawn from the alphabet {KI, KR, SO, SU, BF, BU}, representing the following events, respectively: "key just inserted into ignition", "key just removed from ignition", "seat just became occupied", "seat just became unoccupied", "belt has just been fastened", and "belt has just been unfastened". The output alphabet is {ON, OFF}. The buzzer should go on when ON is output and stay off until OFF is output. 14. Is it possible to construct a finite state transducer that can output the following sequence:1010010001000010000010000001…If it is possible, design one. If it's not possible, why not?Solutions1. L(M) iff the initial state is a final state. Proof: M will halt in its initial state given as input. So: (IF) If the initial state is a final state, then when M halts in the initial state, it will be in a final state and will accept as an element of L(M). (ONLY IF) If the initial state is not a final state, then when M halts in the initial state, it will reject its input, namely . So the only way to accept is for the initial state to be a final state.2. Homework 4 Deterministic Finite Automata 33. Homework 4 Deterministic Finite Automata 4Homework 4 Deterministic Finite Automata 54. (a) (b)Homework 4 Deterministic Finite Automata 6(c)5. b a a,b1 a 2 b 36. (aa)* (bb* bb*a(aa)*) = (aa)*b+( a(aa)*) = all strings of a's and b's consisting of an even number of a's, followed by at least one b, followed by zero or an odd number of a's.7. b a a,b1 2 a 3b8. (a) (b) a (a b)* (b aa) a2 a a1 b 3 b a4 b bHomework 4 Deterministic Finite Automata 79. (a) a a a a b b b b b a b b b a,b a a a a,b(b) ( ab aabb aaabbb aaaabbbb)Homework 4 Deterministic Finite Automata
View Full Document
Unlocking...