Version without JavaScript, read-only: workshops, quizzes and running code are not available here. Full version · Catalogue · Sign in
Lecture notes · chapter 2
Regular expressions
Describing infinite languages finitely. Regular languages, the expressions that denote them, their rules of calculation, and what separates them from the regexes of programming languages.
Which operations to keep?
The goal
We want to describe languages, often infinite ones, by finite and simple formulas: simple to write, to read and, as we shall see, to turn into a program. The idea of the previous chapter was to start from elementary languages and combine them. It remains to choose which ones, and with which operations.
Sorting them out
Let us review the candidates.
| Language or operation | Keep? | Why |
|---|---|---|
| $\emptyset$ | yes | useless at first sight, but we do need to be able to name the empty language |
| $\{\varepsilon\}$ | yes | very useful: “nothing”, “optional” |
| $\{a\}$, for $a \in \Sigma$ | yes | the basic building blocks |
| $L_1 \cup L_2$ | yes | choice |
| $L_1 \cdot L_2$ | yes | sequence |
| $L^*$ | yes | repetition, the only source of infinity |
| $\Sigma^*$ | no | it is $(\{a\} \cup \{b\})^*$: we can already obtain it |
| $L_1 \cap L_2$ | no | we do not need it for the definition (we shall see that nothing is lost) |
| $\overline{L}$, $L_1 \setminus L_2$ | no | same remark |
About $\emptyset$: it is almost useless. $L \cup \emptyset = L$ (it is neutral for union), $L \cdot \emptyset = \emptyset$ (it is absorbing for product), $\emptyset^* = \{\varepsilon\}$. But without it, we could not name the empty language, and some algorithms produce it. We keep it.
The six operations retained are called the regular operations.
Regular languages
“The smallest” means: a language is regular if and only if it is obtained from the basic languages by a finite number of regular operations. This is an inductive definition, and proofs about regular languages will go by induction: we handle the three base cases, then the three inductive cases.
Not all languages are regular: we shall prove in chapter 7 that $\{a^n b^n \mid n \geq 0\}$ is not.
Regular expressions
Syntax
Writing $\{a\} \cdot (\{a\} \cup \{b\})^*$ is tedious. We give ourselves a lighter notation, in which each basic language and each operation has its own symbol.
Semantics
An expression denotes a language. We write $L(e)$ for the language denoted by $e$:
| Expression | Denoted language |
|---|---|
| $\emptyset$ | $L(\emptyset) = \emptyset$ |
| $\varepsilon$ | $L(\varepsilon) = \{\varepsilon\}$ |
| $a$ | $L(a) = \{a\}$ |
| $e + f$ | $L(e + f) = L(e) \cup L(f)$ |
| $ef$ | $L(ef) = L(e) \cdot L(f)$ |
| $e^*$ | $L(e^*) = L(e)^*$ |
Union is written $+$ because it behaves like an addition: it is associative, commutative, with neutral element $\emptyset$, and product distributes over it. The analogy stops there: $e + e = e$, which is nothing like an addition.
A language is therefore regular if and only if it is denoted by at least one regular expression.
A spelling detail, which stops being a detail in an exam: in French we write expression rationnelle; in English, rational or regular expression.
Precedence
To lighten the notation, we fix precedences, as in arithmetic: star first, then product, then union.
The star applies only to what immediately precedes it: $ab^*$ denotes $a$, $ab$, $abb$…, whereas $(ab)^*$ denotes $\varepsilon$, $ab$, $abab$…
Equivalence
Two expressions $e$ and $f$ are equivalent, written $e \equiv f$, if they denote the same language: $L(e) = L(f)$. Here are the equivalences in common use; all of them are proved by going back to the languages.
| Equivalence | Name |
|---|---|
| $e + (f + g) \equiv (e + f) + g$, $\quad e(fg) \equiv (ef)g$ | associativity |
| $e + f \equiv f + e$ | commutativity of union |
| $e + e \equiv e$ | idempotence of union |
| $e + \emptyset \equiv e$ | $\emptyset$ neutral for union |
| $e\varepsilon \equiv \varepsilon e \equiv e$ | $\varepsilon$ neutral for product |
| $e\emptyset \equiv \emptyset e \equiv \emptyset$ | $\emptyset$ absorbing for product |
| $e(f + g) \equiv ef + eg$, $\quad (e + f)g \equiv eg + fg$ | distributivity |
| $\emptyset^* \equiv \varepsilon$, $\quad \varepsilon^* \equiv \varepsilon$ | |
| $(e^*)^* \equiv e^*$, $\quad e^* e^* \equiv e^*$ | |
| $e^* \equiv \varepsilon + ee^*$ | we stop, or we go round once more |
| $(e + f)^* \equiv (e^* f)^* e^*$ |
Product is not commutative: $ab \not\equiv ba$.
Testing the equivalence of two expressions by calculations of this kind requires cleverness, and we never know whether we have exhausted the possibilities. In chapter 6, we shall obtain an algorithm that always answers.
Examples, and precise definitions
Numbers
Over $\Sigma = \{0, 1\}$, the binary numbers: at least one digit.
Over the alphabet of the ten digits, the numbers in base 10:
It is correct, but nobody can read it any more. We shall come back to it with abbreviations.
What is a number?
The previous expression accepts $3$, $7$, $07$ and $007$. Is that what we want? Two definitions are legitimate:
- a number is a non-empty sequence of digits, and $007$ is one;
- a number has no useless leading zero: $0$ is a number, $07$ is not.
The second is written, with $c$ the union of the ten digits and $c'$ that of the nine non-zero digits:
Neither is the “right” one: it depends on the use. In C, 7 and 07 are two valid constants, but 07 is written in octal; 08 is rejected by the compiler, since $8$ is not an octal digit. The C grammar uses yet a third definition. The point of a regular expression is to make the definition precise: once it is written, the question “is $007$ a number?” has an answer.
Abbreviations
Real-world expressions use additional notations. They are not new operations: each one can be written with the six basic ones, so it does not change the set of languages we can describe.
| Notation | Meaning | Example |
|---|---|---|
| $e^+$ | $ee^*$, at least once | $(0 + 1)^+$: the binary numbers |
| $e?$ | $e + \varepsilon$, optional | $0?1$: the words $1$ and $01$ |
| $e^n$ | $e \cdots e$, $n$ times | $(0+1)^8$: a byte |
| $[abc]$ | $a + b + c$, one letter among these | $[+-]$ |
| $[0-9]$ | $0 + 1 + \cdots + 9$, one letter from a range | $[a-zA-Z]$: a letter |
Regular expressions and regexes
The “regexes” of grep, Python or JavaScript descend from regular expressions, but they are not the same objects.
- They search for a factor.
grep 'ab'selects the lines that contain $ab$. The regular expression $ab$ denotes the single word $ab$; the search done bygrepcorresponds to $\Sigma^* ab \Sigma^*$. The anchors^and$are used to require the whole word. - They have extra abbreviations:
.for any letter,\dfor a digit,{2,5}for “from 2 to 5 times”. These remain regular. - Some extensions are not. Backreferences, such as
(a*)b\1, which requires repeating on the right what was read on the left, describe $\{a^n b a^n \mid n \geq 0\}$. This language is not regular (same reasoning as for $a^nb^n$, in chapter 7). This is also why some regexes run in exponential time, which never happens to a regular expression compiled into an automaton (chapter 4).