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 sequenc eof inputs is accepted if the last marble comes out at D. b) Describe the set accepted by the DFA. Solution: a) M = ({A,B,C,D,E,F,G,H,I,J,K,L}, {0,1}, delta, {A}, {A,B,I,J,K,L}) delta(A,0) = E delta(A,1) = D delta(B,0) = F delta(B,1) = A delta(C,0) = G delta(C,1) = B delta(D,0) = H delta(D,1) = I delta(E,0) = C delta(E,1) = H delta(F,0) = D delta(F,1) = J delta(G,0) = A delta(G,1) = K delta(H,0) = B delta(H,1) = L delta(I,0) = G delta(I,1) = B delta(J,0) = C delta(J,1) = H delta(K,0) = D delta(K,1) = J delta(L,0) = A delta(L,1) = K Key: State A corresponds to lever x,y,z positions /// Key: State B corresponds to lever x,y,z positions //\ Key: State C corresponds to lever x,y,z positions /\/ Key: State D corresponds to lever x,y,z positions /\\ Key: State E corresponds to lever x,y,z positions \// Key: State F corresponds to lever x,y,z positions \/\ Key: State G corresponds to lever x,y,z positions \\/ Key: State H corresponds to lever x,y,z positions \\\ Key: State I corresponds to lever x,y,z positions /\/ Key: State J corresponds to lever x,y,z positions \// Key: State K corresponds to lever x,y,z positions \/\ Key: State L corresponds to lever x,y,z positions \// b) Two possible descriptions are All strings ending in a 1, where the number of 1s is even. All strings of length X that either end in a 1 or have an even number of 0s where X mod 4 = 0, or (X-3) mod 4 = 0 (X = 3, 4, 7, 8, 11, 12, ...). 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. Solution: The DFA for strictly ordered Roman numerals is defined below. Transitions not indicated go to a rejecting state. All states, except the starstate, are final (accepting) states. delta(s,C) = C delta(s,L) = L delta(s,X) = X delta(s,V) = V delta(s,I) = I delva(L,X) = X delta(L,V) = V delta(L,I) = I delta(X,X) = XX delta(X,V) = V delta(X,I) = I delta(XX,X) = XXX delta(XX,V) = V delta(XX,I) = I delta(XXX,X) = XXXX delta(XXX,V) = V delta(XXX,I) = I delta(V, I) = I delta(I, I) = II delta(II, I) = III delta(III, I) = IIII 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. Solution: 0,1 +--+ v | +--+ 0 +--+ 0 +====+ |q0|--->|q1|--->||q5|| +--+ /+--+^ +====+ 0,1/ \0,1 v \ +--+ +--+ |q2| |q4| +--+ +--+ \ ^ 0,1\ /0,1 v / +--+ |q3| +--+ 4. Describe in English the languages accepted by the deterministic finite automata shown below. b a +----------+===+---------+ / a ||*|| \ / +------->+===+ \ | / | v / v +-+ +-+ -->|*| |*| +-+ +-+ \ / \ b a,b / +-------->+-+<--------+ |*| +-+ | ^ | | +-+ a,b Solution: The set of all strings beginning with an a and followed by any number of ba pairs. 5. Problem 2.2.1 parts a and b from the textbook. 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 Solution: a) (i) no (ii) yes (iii) no (iv) yes (v) yes b) (i) yes (ii) no (iii) yes (iv) no (v) yes