CS154 Assignment #3
Due Monday, January 31, 2000, 3:15PM
Because the first project is due on 2/2, this will be a ``half
assignment,'' worth 50 points.

(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.

(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?

(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.