Question

What are the equivalence classes for a ∗ b ∗ ?

• How many equivalence classes are there?

• Make each one into a state and show how one can construct a minimal deterministic finite automaton from them.

• Explain how to choose the start state and accepting states and how to draw the arrows.

• The resulting automaton is minimal for this language. How about for {a n b n : n ≥ 0}? What are the equivalence classes?

Answer 1

For a*b*:

The idea is to find all the substrings that can be generated using the symbol and to traverse through eacch to reach a different state on each input, i.e if q0 -a-> q1 and q0 -b-> q1 then we take them as one equivalence class and not two.

The following table shows all the sets possible and we can see that there are four quivalence classes.

For aⁿbⁿ

As we can see from its production, ({}, ab, aabb, aaabbb, aaaabbbb....) this is repeated patter of equal length over a and b but there is no way to draw its finite automate as we can not ensure how many a's are there before we start printing b, for that we need a stack to count and stack is not used in FA, instead its used in Pushdown automata, hence the equivalance classes of it are two (a preceeding b and only b....) but its automation is not finite.