Martin

If $\Sigma$ is an alphabet, the set $\mathcal R$ of regular languages over $\Sigma$ is defined as follows.

1. The language $\varnothing$ is an element of $\mathcal R$, and for every $a\in\Sigma$, the language $\{a\}$ is in $\mathcal R$.
2. For any two languages $L_1$ and $L_2$ in $\mathcal R$, the three languages

are elements of $\mathcal R$.

The language $\{\Lambda\}$ is a regular language over $\Sigma$, because $\varnothing^*=\{\Lambda\}$. If $\Sigma=\{a,b\}$, then $L_1=\{a,b\}^*\{aa\}$ can be obtained from the definition by starting with the two languages $\{a\}$ and $\{b\}$ and then using the recursive statement in the definition four times: The language $\{a,b\}$ is the union $\{a\}\cup\{b\}$; $\{aa\}$ is the concatenation $\{a\}\{a\}$; $\{a,b\}^*$ is obtained by applying the Kleene star operation to $\{a,b\}$; and the final language is the concatenation of $\{a,b\}^*$ and $\{aa\}$.

A regular language over $\Sigma$ has an explicit formula. A regular expression for the language is a slightly more user-friendly formula. The only differences are that in a regular expression, parentheses replace $\{\}$ and are omitted whenever the rules of precedence allow it, and the union symbol $\cup$ is replaced by $+$. Here are a few examples (see Example 3.5 for a discussion of the last one):

When we write a regular expression like $\Lambda$ or $aab$, which contains neither $+$ nor $*$ and corresponds to a one-element language, the regular expression looks just like the string it represents. A more general regular expression involving one or both of these operations can't be mistaken for a string; we can think of it as representing the general form of strings in the language. A regular expression describes a regular language, and a regular language can be described by a regular expression.

We say that two regular expressions are equal if the languages they describe are equal. Some regular-expression identities are more obvious than others. The formula

is true because the language corresponding to $a^*b^*$ contains both $a$ and $b$. The formula

is true because the first term on the left side corresponds to the strings in $\{a,b\}^*$ that contain the substring $ab$ and the second term, $b^*a^*$, corresponds to the strings that don't.

A string with an odd number of $a$'s has at least one $a$, and the additional $a$'s can be grouped into pairs. There can be arbitrarily many $b$'s before the first $a$, between any two consecutive $a$'s, and after the last $a$. The expression

is not correct, because it doesn't allow $b$'s between the second $a$ in one of the repeating pairs $ab^*a$ and the first $a$ in the next pair. One correct regular expression describing the language is

The expression

is also not correct, because it doesn't allow strings with just one $a$ to end with $b$, and the expression

corrects the mistake. Another correct expression is

All of these could also be written with the single $a$ on the right, as in

If a string does not contain the substring $aa$, then every $a$ in the string either is followed immediately by $b$ or is the last symbol in the string. If the string ends with $b$, then every $a$ is followed immediately by $b$. Therefore, every string in the language $L$ of strings that end with $b$ and do not contain $aa$ matches the regular expression $(b+ab)^*$. This regular expression does not describe $L$, however, because it allows the null string, which does not end with $b$. At least one of the two strings $b$ and $ab$ must occur, and so a regular expression for $L$ is

One of the regular expressions given in Example 3.2, $b^*a(b+ab^*a)^*$, describes the language of strings with an odd number of $a$'s, and the final portion of it, $(b+ab^*a)^*$, describes the language of strings with an even number of $a$'s. We can interpret the two terms inside the parentheses as representing the two possible ways of adding to the string without changing the parity (the evenness or oddness) of the number of $a$'s: adding a string that has no $a$'s, and adding a string that has two $a$'s. Every string $x$ with an even number of $a$'s has a prefix matching one of these two terms, and $x$ can be decomposed into nonoverlapping substrings that match one of these terms.

Let $L$ be the subset of $\{a,b\}^*$ containing the strings $x$ for which both $n_a(x)$ and $n_b(x)$ are even. Every element of $L$ has even length. We can use the same approach to find a regular expression for $L$, but this time it's sufficient to consider substrings of even length. The easiest way to add a string of even length without changing the parity of the number of $a$'s or the number of $b$'s is to add $aa$ or $bb$. If a nonnull string $x\in L$ does not begin with one of these, then it starts with either $ab$ or $ba$, and the shortest substring following this that restores the evenness of $n_a$ and $n_b$ must also end with $ab$ or $ba$, because its length is even and strings of the form $aa$ and $bb$ don't change the parity of $n_a$ or $n_b$.

The conclusion is that every nonnull string in $L$ has a prefix that matches the regular expression

and that a regular expression for $L$ is

In Example 2.9 we built a finite automaton to carry out a very simple version of lexical analysis: breaking up a part of a computer program into tokens, which are the basic building blocks from which the expressions or statements are constructed. The last two sections of this chapter are devoted to proving that finite automata can accept exactly the same languages that regular expressions can describe, and in this example we construct regular expressions for two classes of tokens.

An identifier in the C programming language is a string of length 1 or more that contains only letters, digits, and underscores ("$\_$") and does not begin with a digit. If we use the abbreviations $l$ for "letter," either uppercase or lowercase, and $d$ for "digit," then $l$ stands for the regular expression

and $d$ for the regular expression

(which has nothing to do with the integer 45), and a regular expression for the language of C identifiers is

Next we look for a regular expression to describe the language of numeric "literals," which typically includes strings such as $14$, $+1$, $-12$, $14.3$, $-.99$, $16.$, $3\mathrm E14$, $-1.00\mathrm E2$, $4.1\mathrm E{-1}$, and $.3\mathrm E{+2}$. Let us assume that such an expression may or may not begin with a plus sign or a minus sign; it will contain one or more decimal digits, and possibly a decimal point, and it may or may not end with a subexpression starting with $\mathrm E$. If there is such a subexpression, the portion after $\mathrm E$ may or may not begin with a sign and will contain one or more decimal digits.

Our regular expression will involve the abbreviations $d$ and $l$ introduced above, and we will use $s$ to stand for "sign" (either $\Lambda$ or a plus sign or a minus sign) and $p$ for a decimal point. It is not hard to convince yourself that a regular expression covering all the possibilities is

In some programming languages, numeric literals are not allowed to contain a decimal point unless there is at least one digit on both sides. A regular expression incorporating this requirement is

Other tokens in a high-level language can also be described by regular expressions, in most cases even simpler than the ones in this example. Lexical analysis is the first phase in compiling a high-level-language program. There are programs called lexical-analyzer generators; the input provided to such a program is a set of regular expressions describing the structure of tokens, and the output produced by the program is a software version of an FA that can be incorporated as a token-recognizing module in a compiler. One of the most widely used lexical-analyzer generators is lex, a tool provided in the Unix operating system. It can be used in many situations that require the processing of structured input, but it is often used together with yacc, another Unix tool. The lexical analyzer produced by lex creates a string of tokens; and the parser produced by yacc, on the basis of grammar rules provided as input, is able to determine the syntactic structure of the token string. (yacc stands for yet another compiler compiler.)

Regular expressions come up in Unix in other ways as well. The Unix text editor allows the user to specify a regular expression and searches for patterns in the text that match it. Other commands such as grep (global regular expression print) and egrep (extended global regular expression print) allow a user to search a file for strings that match a specified regular expression.