CSE 237, Homework 2 (DFAs)
due 2/08/06 in class

1.Please start each problem on a new sheet.

2. Do not turn in problems whose answer is in the textbook.

 

Problem 1

(a) Problem 1.1 from the textbook (answer in textbook)
(b) For each of the two DFAs in (a), give a table-based representation
(c) For each of the two DFAs in (a), give a set-based representation

Problem 2.

For each of the following languages, provide a diagram of a DFA which accepts this language (use descriptive names for states, if possible).  For each DFA, show its computation (as a sequence of transitions) for the input string 01, and for the input string 001.

(a) All strings over {0,1} containing the number of 0's is divisible by 2 and the number of 1's is NOT divisible by 3.
(b) All strings over {0,1} where "0" is the third digit from the end.
(c) All strings over {0,1} which do NOT have a substring 001.

Hint: To "debug" your DFAs, look for strings they accept but should not, or strings they do not accept but should.

Problem 3.

(a) Let M1 be some DFA (Q, S, d, q0, F1) and M2 be some DFA (Q, S, d, q0, F2), where F1 U F2 = Q (the two DFAs are the same except for their sets of final states).  Prove that L(M1) U L(M2) = S*, by using definitions.

(b) Suppose that in (a) above M1 and M2 were not DFAs but NFAs. Is the above claim still true? Please prove that it is not, by finding a counterexample (the simpler one the better).