Building the Standard Automaton for a Language

Consider the language L = (bb ∪ aa)* ∪ (ab)*. To construct the standard automaton for L we need to identify the equivalence classes of {a,b} under ≈L. First we make some useful observations:

  1. If x≈y then |x| and |y| are either both even or both odd.
  2. If |x| is even and |x|≥ 2, then xz ∈ L iff either x and z are both in (bb ∪ aa)* or x and z are both in (ab)*

The equivalence classes are as follows:

[e]

= e ⊆ L Suppose x≈e and x ≠ e, then by (1), |x| is even. Let z1 = ab, then ez1 ∈ L so by (2) x ∈ (ab)*. Let z2 = aa, then ez ∈ L, so by (2) x ∈ (bb ∪ aa)*, a contradiction. So if x≈e then x = e.
[a]
 = a Suppose x≈a and x ≠ a, then x ≠ b since aa ∈ L but ba ∉ L. So by (1) |x| ≥ 3. If x ends in b, xa ends in ba and is therefore not in L, but aa ∈ L contradicting the fact that x≈a. If x ends in a there are four possibilities:
  • x = waaa for some w. In this case xb ∉L; but ab ∈ L - a contradiction
  • x = waba for some w. In this case xa ∉L; but aa ∈ L - a contradiction
  • x = wbaa for some w. In this case xa ∉L; but aa ∈ L - a contradiction
  • x = wbba for some w. In this case xb ∉L; but ab ∈ L - a contradiction

[b]

 = (bb ∪ aa)*b bz ∈ L iff z ∈ b(bb ∪ aa)*. Clearly xz ∈ L iff x ∈ (bb ∪ aa)*b

[aa]

= (bb ∪ aa)*(bb ∪ aa) ⊆ L

 Since |aa| = 2, by (2) above aaz ∈ L iff z ∈ (bb ∪ aa)*. If x≈aa, then by (1), |x| is even, and x ≠ e (shown above), so |x|≥ 2 and therefore by (2), xz ∈ L iff x ∈ (bb ∪ aa)*. But x ≠ e, so xz ∈ L iff x ∈ (bb ∪ aa)*(bb ∪ aa).
[ab]
 = (ab)*ab ⊆ L Similar to the argument for [aa]
[aba]
 = (ab)*aba abaz ∈ L iff z ∈ b(ab)*, so if x≈aba then x ∈ (ab)*a. However x cannot be a, since [a]=a, so x must be in (ab)*aba.
[aaa]
 = (bb ∪ aa)* (bb ∪ aa)b Similar to the argument for [aba]
[ba]
 = (ba ∪ (bb ∪ aa)*(bb ∪ aa)(ab ∪ ba) ∪ (ab)*ab(aa ∪ b))Σ* All the ways of constructing an "irredeemable" string!

Now we build the automaton using these classes as states, as follows: