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


Yes, it recognizes strings made out of groups of equal number of a's and b's. But it does not match all possible strings with an equal number of a's and b's.

For example aaaabbbb is not matched.


Rule 13:  Quantifiers

Here is a regular expression that matches strings that contain three o's in a row:


and here is a shorthand way to write the same expression:


The subexpression o{3} means to match three characters 'o' in a row.

Here is the non-deterministic finite automaton for both of these. It is non-deterministic because the transition "any character" includes character 'o' and so there are two choices for the same character.

automaton to recognize .*ooo.*

This automaton does not have a counter. It merely has three states in a row that have 'o' transitions. It is easy to change this automaton into a deterministic automaton. Try this as an exercise.


Write a RE that matches strings that start with five A's and end with five Z's.