Homework #3 1. Consider the toy shown below. A marble is dropped in at A or B. Levers x, y, and z cause the marble to fall either to the left or right. Whenever a marble encounters a lever, it causes the lever to change state, so that the next marble to encounter the lever will take the opposite branch. | A | | B | | | | | | x | | y | / / \ / / \ / \ / \ / /\ \ / /\ \ / / \ \/ / \ \ / / \ z / / \ \ \ \ / / \ / / \ \ / /\ \ / / \ \/ / \ \/ / \ / \ / \ / \ / | | | | | | | | | C | | D | a) Model this toy by a DFA. Denote a marble in at A by a 0-input and a marble in at B by a 1-input. A sequence of inputs is accepted if the last marble comes out at D. b) Describe the set accepted by the DFA. 2. Recall (part of) the Roman numeral system: I = 1, V = 5, X = 10, L = 50, C = 100. Recall also that in a valid Roman numeral, strings such as IIIII or VV are not allowed, since there are alternative representations using larger values, such as V and X, respectively. Draw a DFA that accepts exactly the set of valid Roman numerals between 1 and 100 that are strictly ordered: that is, no letter may appear after a letter that has a smaller value. Thus 9 must be represented by VIII rather than by IX. The alphabet for your DFA should be {I, V, X, L, C}. You should adopt the convention that edges not drawn lead to a unique "dead" or "trap" state, which is nonaccepting, and which has edges leading back to itself on any input. Also, be sure that your DFA doesn't accept any numeral with value 101 or more. 3. Give a NFA that accepts the following language over {0,1}: the set of strings such that some two 0s are separated by a string whose length is 4i, for some i >= 0. 4. Describe in English the languages accepted by the deterministic finite automata shown below. b a +----------+===+---------+ / a ||*|| \ / +------->+===+ \ | / | v / v +-+ +-+ -->|*| |*| +-+ +-+ \ / \ b a,b / +-------->+-+<--------+ |*| +-+ | ^ | | +-+ a,b 5. Which of the following strings are accepted by these nondeterministic finite automata? a) +===+ a +-+ b +-+ a +-+ -->||*||------->|*|------->|*|------->|*| +===+ +-+ +-+ +-+ ^ ^ | | a | | b | e | b | \ | | | \ v | +-+ +-----+-+ | |*|<--------|*|<--------+ +-+ b +-+ (i) aa (ii) aba (iii) abb (iv) ab (v) abab b) b +-+ | | v | +-+ b +-+ b +===+ -->|*|------->|*|------->||*|| +-+ +-+ +===+ | e | | v +-+ +===+ |*|------->||*|| +-+ a +===+ ^ | | | +-+ b (i) ba (ii) ab (iii) bb (iv) b (v) bba