3.2: Regular Expressions

Though we have used the term string throughout to refer to a sequence of symbols from an alphabet, an alternative term that is frequently used is word. The analogy seems fairly obvious: strings are made up of “letters” from an alphabet, just as words are in human languages like English. In English, however, there are no particular rules specifying which sequences of letters can be used to form legal English words—even unlikely combinations like ghth and ckstr have their place. While some formal languages may simply be random collections of arbitrary strings, more interesting languages are those where the strings in the language all share some common structure:

\(L_{1}=\left\{x \in\{a, b\}^{*} | n_{a}(x)\right\} ; L_{2}=\{\text { legal Java identifiers }\}\);\(L_{3}=\{\text { legal } \mathrm{C}++\text { programs }\}\).

In all of these languages, there are structural rules which determine which sequences of symbols are in the language and which aren’t. So despite the terminology of “alphabet” and “word” in for- mal language theory, the concepts don’t necessarily match “alphabet” and “word” for human languages. A better parallel is to think of the alphabet in a formal language as corresponding to the words in a human language; the words in a formal language correspond to the sentences in a human language, as there are rules (grammar rules) which determine how they can legally be constructed.

One way of describing the grammatical structure of the strings in a lan- guage is to use a mathematical formalism called a regular expression. A regular expression is a pattern that “matches” strings that have a partic- ular form. For example, consider the language (over alphabet \(\Sigma=\{a, b\} )\). \(L=\{x | x \text { starts and ends with } a\}\) What is the symbol-by-symbol struc- ture of strings in this language? Well, they start with an a, followed by zero or more a’s or b’s or both, followed by an a. The regular expression \(a \cdot(a | b)^{*} \cdot a\) is a pattern that captures this structure and matches any string in L (· and ∗ have their usual meanings, and | designates or.1) Conversely, consider the regular expression (a · (a | b)∗ ) | ((a | b)∗ · a). This is a pattern that matches any string that either has the form “a followed by zero or more a’s or b’s or both” (i.e. any string that starts with an a) or has the form “zero or more a’s or b’s or both followed by an a” (i.e. any string that ends with an a). Thus the regular expression generates the language of all strings that start or end (or both) in an a: this is the set of strings that match the regular expression.

Here are the formal definitions of a regular expression and the language generated by a regular expression:

Definition 3.2.

Let \(\Sigma\) be an alphabet. Then the following patterns are regular expressions over \(\Sigma :\)

1. \(\Phi\) and \(\varepsilon\) are regular expressions;

2. \(a\) is a regular expression, for each \(a \in \Sigma\)

3. if r1 and r2 are regular expressions, then so are r1 | r2, r1 · r2, r1∗and (r1) (and of course, r2∗ and (r2)). As in concatenation of strings, the · is often left out of the second expression. (Note: the order of precedence of operators, from lowest to highest, is | , ·, ∗.)

No other patterns are regular expressions.

Definition 3.3.

The language generated by a regular expression r, denoted L(r), is defined as follows:

1. \(L(\Phi)=\emptyset\) , i.e. no strings match \(\Phi ;\)
2. \(L(\varepsilon)=\{\varepsilon\},\) i.e. \(\varepsilon\) matches only the empty string;
3. \(L(a)=\{a\},\) i.e. a matches only the string \(a\) ;

4. \(L\left(r_{1} | r_{2}\right)=L\left(r_{1}\right) \cup L\left(r_{2}\right),\) i.e. \(r_{1} | r_{2}\) matches strings that match \(r_{1}\) or \(r_{2}\) or both;

5. \(L\left(r_{1} r_{2}\right)=L\left(r_{1}\right) L\left(r_{2}\right),\) i.e. \(r_{1} r_{2}\) matches strings of the form "something that matches \(r_{1}\) followed by something that matches \(r_{2} "\)

6. \(L\left(r_{1}^{*}\right)=\left(L\left(r_{1}\right)\right)^{*},\) i.e. \(r_{1}^{*}\) matches sequences of 0 or more strings each of which matches \(r_{1}\) .

7. \(L\left(\left(r_{1}\right)\right)=L\left(r_{1}\right),\) i.e. \(\left(r_{1}\right)\) matches exactly those strings matched by
\(r_{1}\)

Example 3.7. Let \(\Sigma=\{a, b\}\) and consider the regular expression r = \(a^{*} b^{*} .\) What is \(L(r) ?\) Well, \(L(a)=\{a\}\) so \(L\left(a^{*}\right)=(L(a))^{*}=\{a\}^{*},\) and \(\{a\}\) is the set of all strings of zero or more a's, so \(L\left(a^{*}\right)=\{\varepsilon, a, a a, a a a, \ldots\}\). Similarly, \(L\left(b^{*}\right)=\{\varepsilon, b, b b, b b b, \ldots\} .\) since \(L\left(a^{*} b^{*}\right)=L\left(a^{*}\right) L\left(b^{*}\right)=\{x y | x \in\) \(L\left(a^{*}\right) \wedge y \in L\left(b^{*}\right) \},\) we have \(L\left(a^{*} b^{*}\right)=\{\varepsilon, a, b, a a, a b, b b, a a a, a a b, a b b, b b b, \dots\}\), which is the set of all strings of the form “zero or more a’s followed by zero or more b’s”.

Example 3.8. Let \(\Sigma=\{a, b\},\) and consider the regular expression \(r=\) \((a|a a| a a a)(b b)^{*} .\) since \(L(a)=\{a\}, L(a a)=L(a) L(a)=\{a a\}\). Similarly, \(L(a a a)=\{a a a\}\) and \(L(b b)=\{b b\} .\) Now \(L(a|a a| a a a)=L(a) \cup\)\(L(a a) \cup L(a a a)=\{a, a a, a a a\},\) and \(L\left((b b)^{*}\right)=(L((b b)))^{*}=(L(b b))^{*}\) (the last equality is from clause 7 of Definition \(3.3 ),\) and \((L(b b))^{*}=\{b b\}^{*}=\) \(\{\varepsilon, b b, b b b b, \ldots\} .\) So \(L(r)\) is the set of strings formed by concatenating \(a\) or \(a a\) or aaa with zero or more pairs of \(b^{\prime} \mathrm{s} .\)

Definition 3.4.

A language is regular if it is generated by a regular expression.

Clearly the union of two regular languages is regular; likewise, the con- catenation of regular languages is regular; and the Kleene closure of a reg- ular language is regular. It is less clear whether the intersection of regular languages is always regular; nor is it clear whether the complement of a regular language is guaranteed to be regular. These are questions that will be taken up in Section 3.6.

Regular languages, then, are languages whose strings’ structure can be described in a very formal, mathematical way. The fact that a language can be “mechanically” described or generated means that we are likely to be able to get a computer to recognize strings in that language. We will pursue the question of mechanical language recognition in Section 3.4, and subsequently will see that our first attempt to model mechanical language recognition does in fact produce a family of “machines” that recognize exactly the regular languages. But first, in the next section, we will look at some practical applications of regular expressions.

Exercises

1. Give English-language descriptions of the languages generated by the follow- ing regular expressions.

a) \((a | b)^{*} \quad\) b) \(a^{*} | b^{*} \quad\) c) \(b^{*}\left(a b^{*} a b^{*}\right)^{*} \quad\) d) \(b^{*}\left(a b^{*}\right)\)

2. Give regular expressions over \(\Sigma=\{a, b\}\) that generate the following languages.

a) \(L_{1}=\left\{x | x \text { contains } 3 \text { consecutive } a^{\prime} s\right\}\)
b) \(L_{2}=\{x | x \text { has even length }\}\)
c) \(L_{3}=\left\{x | n_{b}(x)=2 \bmod 3\right\}\)
d) \(L_{4}=\{x | x \text { contains the substring aaba }\}\)
e) \(L_{5}=\left\{x | n_{b}(x)<2\right\}\)
f) \(L_{6}=\{x | x \text { doesn't end in aa }\}\)

3. Prove that all finite languages are regular.