CS154 Assignment #3

Due Monday, January 31, 2000, 3:15PM

1. (20 pts.) Let us consider all possible DFA's with three states; call them p, q, and r. State r is accepting, and the other two are not. We are not going to specify a start state. The input symbols are 0 and 1, only. There are 729 different transition functions that this DFA could have, since each of the three states can have a transition to any of the three states on each of two input symbols. We thus have six choices, each from three objects (states), for a total of 3^6 = 729 transition functions. Some of these transition functions cause states p and q to be equivalent. In how many of these 729 automata are p and q equivalent? Explain your reasoning.

2. (15 pts.) Give an algorithm to decide whether a given DFA accepts at least 100 different strings. Hint: We learned how to test if the language of a DFA is infinite. You may refer to this test in your algorithm and need not give the details. If a language is infinite, then surely it accepts at least 100 strings. What if the language is finite? Just knowing it is finite does not allow us to test strings systematically. We could face a situation where, say, we have found 60 strings that the DFA accepts, and we keep testing longer and longer strings, and don't find any more that are accepted, but we worry that there are 40 strings even longer that the DFA will accept. How do you put a limit on how long an accepted string can be if the DFA's language is finite?

3. (15 pts.) Give a CFG that generates the set of strings of the form wcx, where w and x are strings of a's and b's, w and x are of the same length, but x is not the reverse of w. For each of your variables, give an intuitive explanation of what strings they generate.