CSE 468, Fall 98: Solutions of Midterm 1

Exercise 1

  1. The following is the minimum-state FA for the given language:

  2. The following table proves that the above FA is really minimum-state:

    The first iteration distinguishes (by marking with 1) the pair of states in which one is acceptance and the other is not.

    The second iteration distinguishes (by marking with 2) 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 1 and 3 because of the b-transition, and 2 and 4, also because of the b-transition.

    Since all states are distinguished, the FA is minimum.

Exercise 2

  1. L1 is regular. In fact, it is the language of the strings of even length on {a,b}, and can be represented by the regular expression ((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 a string in L2 such that |x| > n. By definition, |x| = 2m for some m. Let uvw = x with |v| > 0 and |uv| smaller than or equal to n. Let h = |x|. We have that |uvvw| = 2m + h. Finally, observe that uvvw cannot be an element of L2, because if it were, than we should have that 2m + h = 2r, for some r. But the only possibilities for this equality to hold would be that either h = 0 or h greater than or equal to 2m, and these are both ruled out by the hypotheses on the lenght of |v|.

Exercise 3

Yes, it is decidable. A simple decision algorithm is the following:

We know that the minimum state FA for the langauge Sigma* is an automaton M' with only one state q, which is an acceptance state, and all the transitions (for each symbol in Sigma) going from q to q.

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