CSE 468, Fall 98: Solutions of Midterm 1
Exercise 1
- The following is the minimum-state FA for the given language:
- 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
- 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))*.
- 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'.