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


No. Then the automaton would accept strings that start with any number of 'a'.

Basic Regular Expressions: Kleene Star

Rule 6. ZERO or More Instances

The character * in a regular expression means "match the preceding character zero or many times". For example A* matches any number (including zero) of character 'A'.

Regular ExpressionMatches
a* ZERO or more 'a'
ba* b, ba, baa, baaa, baaaa, ...
[ab]* Ø, a, ab, aaa, ababb, bbb, ...
zero or more characters, each character an 'a' or 'b'
[^0-9]* Ø, A, ABC, zw$nn, ...
zero or more characters, no character a digit
a*b* Ø, a, aaa, aaab, abbb, b, bbb, ...
zero or more 'a', followed by zero or more 'b'

In the above, Ø is the "empty string" — the string containing no characters. This sounds odd, but it is like a bank account with no money. It is useful to talk about the account, even it it is empty.

Stephen Kleene (1909-1994) was one of the early investigators of regular expressions and finite automata. The "Kleene star" is often used in computer science. It is a phrase you should know. Kleene pronounced his name "klay-nee", but often people pronounce it "klee-nee".


Does [fr]*og match "frog" ?