go to previous page   go to home page   go to next page

Answer:

Can't be done.


Counting

This can't be done with a basic RE nor with a regular finite automaton. To do that the RE (or automaton) would need a counter that was incremented or decremented as a's and b's were scanned. But regular finite automata have no mechanism for doing that. (An abstract machine called a pushdown automaton does, however.) You could easily write a program that checks if a string has an equal number of a's and b's. But that would go beyond the definition of a finite automaton.

There are many sets of strings that can not be described with regular expressions. This is one of them.

Some regular expressions describe strings that have an equal number of a's and b's, but those a's and b's must appear in a particular arrangement. For example, (ab)+ describes strings like "ababab" and "abababab" that have equal numbers of both characters, but this is done by ensuring that every 'a' is immediately followed by a 'b', not by using counters.

A rule of thumb is that "automata don't have counters" (and neither do basic regular expressions). The trick question requires a counter (or two). This is not allowed in basic regular expressions.

However, an automaton can recognize any finite set of strings. Consider the set "strings of up to 4 characters, composed of an equal number of 'a' and 'b'". There is a regular expression (and a finite automaton) for that language. One way to do it is for the regular expression to explicitly list each possible string:

ab|ba|aabb|abba|abab|bbaa|baba|baab   

The same trick can be used for "strings of up to N characters (with some characteristic)". As long as N is finite, then a regular expression can explicitly list each string in the set. The expression might be very long (and useless for practical purposes). An automaton could be built to match the expression (and would also be big and useless).


QUESTION 15:

Does the following RE match strings that have an equal number of a's and b's ?

(ab|ba|aabb|abba|abab|bbaa|baba|baab)+