##
*CSE 468, Fall 2000: Solutions of Midterm 1
*

## Exercise 1

The following is the minimum-state FA for the given langauge:
## Exercise 2

The following table proves that the above FA is really minimum-state:
The first iteration distingues (by marking with 1)
the pair of states in which one is acceptance and the other is not.

The second and third iterations distinguish (mark with 2 and 3 respectively) the pair of states
for which there is a transition (with the same input) to states already
distinguished in previous iteration.
Thus the second transition distinguishes 2 and 3 because of the b-transition,
and 3 and 4, also because of the b-transition. The third iteration distinguishes
2 and 4 because of both the a and the b transitions.

Since all states are distinguished, the FA is minimum.

## Exercise 3

- L
_{1} is regular. In fact, it is the language of the strings
of odd length on {a,b}, and can be represented by the regular expression
(a + b)((a + b)(a + b))^{*}.

- L
_{2} is not regular. We can prove it by using the Pumping Lemma.
Let n be a (positive) number. Let x be the string a^{n}b^{n}.
By definition, x belongs to L_{2} and |x| > n.
Let uvw = x with |v| > 0 and |uv| < n. We have that v = a^{h} for some
h > 0. Now observe taht uvvw = a^{n+h}b^{n}, which means that
uvvw cannot belong to L_{2}. But this contradicts the Pumping Lemma, hence
L_{2} cannot be regular.

## Exercise 4

Yes, it is decidable. A simple decision algorithm is the following:
We know that the minimum state FA for the language a^{*} is the following
automaton M' (where a, b, c, ... represent all the symbols of Sigma).

Therefore, given a FA M, it is sufficient to reduce M to its minimum-state FA M", and then check whether M" is isomorphic (namely, identical except maybe the
name of the state) to M'.