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

Answer:

Yes. There are many formal languages that cannot be described by finite automata, and therefore can not be described by regular expressions, either.

For example, the formal syntax of Java can not be described by any finite automata.


Basic Regular Expressions

The simplest regular expression consists of the exact characters of the string that it is intended to match. The regular language defined by the expression consists of only that one string. Upper and lower case letters are regarded as different symbols.

Rule 1.  Sequence of Characters: Exact Match

Regular ExpressionMatchesDoes Not MatchDoes Not Match
turtle "turtle" "Turtle" " turtle"
Dagmar "Dagmar" "mar" "D a g m a r"
a x "a x" "ax" " a x "

Characters in the regular expression match characters in the string one by one, in sequence. Don't think of whole words being matched all at once.

The last regular expression contains a space surrounded by two letters. The space character in the RE matches the space in the string that it matches, "a x".


QUESTION 3:

What regular language is described by the RE turtle ?