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

  1. L1 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))*.

  2. L2 is not regular. We can prove it by using the Pumping Lemma. Let n be a (positive) number. Let x be the string anbn. By definition, x belongs to L2 and |x| > n. Let uvw = x with |v| > 0 and |uv| < n. We have that v = ah for some h > 0. Now observe taht uvvw = an+hbn, which means that uvvw cannot belong to L2. But this contradicts the Pumping Lemma, hence L2 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'.