Fall 98, CSE 468: Solution of Assignment 3

Exercise 1

The regular expression is: (aba)^*
The equivalence classes associated to the indistinguishability relation are:
- [lambda] = {(aba)ⁿ | n >= 0}
- [a] = {(aba)ⁿa | n >= 0}
- [ab] = {(aba)ⁿab | n >= 0}
- [b] = {(aba)ⁿbx | n >= 0, x in {a,b}^*} union {(aba)ⁿaax | n >= 0, x in {a,b}^*}
M is not the minimum FA for L(M). The minimum FA for L(M), M', has four states only. M' can be constructed either on the basis of the partition given above, or by applying the Algorithm 5.1 in Martin's book to M. We give here the solution based on the first technique: The states of M' are: {[lambda],[a],[ab],[b]}. The initial state is [lambda], and [lambda] is also the only acceptance state. The transition relation is:
```
   Delta([lambda],a) = [a]   Delta([lambda],b) = [b] 
   Delta([a],a) = [b]        Delta([a],b) = [ab] 
   Delta([ab],a) = [lambda]  Delta([ab],b) = [b] 
   Delta([b],a) = [b]        Delta([b],b) = [b] 
```

Exercise 2

The problem is decidable. One possible decision algorithm is the following:

Construct the FA N recognizing E (using the algorithm seen in the book)
Minimize N (using the algorithm seen in the book). Let N' be the minimum FA obtained in this way
Minimize M. Let M' be the minimum FA obtained in this way
Check is M' and N' are isomorphic, i.e. check whether there exists a 1-to-1 mapping between the states of M' and the states of N' which
- is preserved by the transition relations
- maps the initial state of M' into the initial state of N',
- maps acceptance states of M' into acceptance states of N',
- maps non-acceptance states of M' into non-acceptance states of N'.
This check can simply be done by trying all possible 1-to-1 correspondences between the states of M' and the states of N' (note that this can be done in finite time, because the number of states is finite, hence also all the possible correspondences are finite).

The answer to the question "Is L(E) = L(M) ?" is "yes" if M' and N' are isomorphic, "no" otherwise.

Exercise 3

The language is not regular. This can be proved either by using the Myhill-Nerode theorem, or by using the pumping lemma. We give here the solution based on the first approach.

Consider the strings a^m and aⁿ, with m different from n. These two strings are distinguishable, in fact for z = b^m+1c a^mz is in L while aⁿz is not in L. Therefore there are infinitely many different equivalence classes associated to (the indistinguishability relation given by) L, and therefore there cannot be any FA recognizing L.

Exercise 4

L is not representable as a regular expression, because it is not a regular language. To show this, we can use again the Myhill-Nerode theorem (note that the pumping lemma is not useful here): Consider the strings (^m and (ⁿ, with m different from n. Observe that (^ma₁)^m is in L while (ⁿa₁)^m is not in L. As before, we conclude that there is no FA accepting L.

A possible grammar with the required properties is the following:

 
   E -> E + T | T
   T -> FT | F
   F -> F^* 
      | (E) 
      | Lambda 
      | Emptyset
      | a₁ | a₂ | ... | a_n