Regular expressions

Why it exists

A DFA or NFA describes a regular language by a machine; a regular expression describes it by a formula, which is the form people and programs prefer for searching text and for specifying the tokens of a language. GATE asks both directions: write an expression for a described language, and decide what language an expression describes or which of several expressions are equivalent.

Prerequisites

You need NFAs and languages as sets of strings (NFA); the equivalence of the two notations is the next page (regex and automata).

Precise definitions

Let $\Sigma$ be an alphabet. Regular expressions over $\Sigma$ and their languages $L(r)$ are defined together by induction:

A language is regular iff it is $L(r)$ for some regular expression $r$ (and, by the next page, iff some DFA or NFA accepts it).

Precedence (strongest first): star, then concatenation, then union. So $a \mid b c^*$ means $a \mid (b (c^*))$, and $a b^*$ is $a (b^*)$, not $(ab)^*$.

Derived forms. $r^+ = r r^*$ (one or more), $r? = r \mid \varepsilon$ (zero or one), and $r^k = r r \cdots r$ ($k$ copies).

Notation warning. This site writes union as $\mid$. Sipser writes $\cup$ and many GATE papers write a plus sign: in a GATE paper $a + b$ usually means "$a$ or $b$", and $a^+$ is a superscript plus meaning "one or more". Read the question's convention before anything else.

Nullable. $\varepsilon \in L(r)$ exactly when $r$ is nullable: $\varepsilon$ and $r^*$ are nullable; a symbol and $\emptyset$ are not; $r \mid s$ is nullable if either is; $r s$ is nullable if both are.

How it works

Reading an expression

Take the language of $r$ piece by piece.

• $(a \mid b)^*$: every string over $\{a, b\}$, including $\varepsilon$.
• $a^* b^*$: some $a$'s followed by some $b$'s; equivalently the strings that do not contain $ba$.
• $(ab)^*$: $\varepsilon$, $ab$, $abab$, $\ldots$
• $(a \mid b)^* a b b$: strings that end in $abb$.
• $a (a \mid b)^* a \mid a$: nonempty strings that start with $a$ and end with $a$ (the single string $a$ is added by the last alternative).

The special cases

$\emptyset$ and $\varepsilon$ are different: $L(\emptyset)$ has no string, $L(\varepsilon)$ has one, the empty string. Therefore

$r \emptyset = \emptyset r = \emptyset, \qquad r \varepsilon = \varepsilon r = r, \qquad r \mid \emptyset = r, \qquad \emptyset^* = \varepsilon^* = \varepsilon.$

Algebraic laws: which hold

Union is commutative, associative and idempotent ($r \mid r = r$). Concatenation is associative but not commutative. Concatenation distributes over union on both sides. For star: $(r^*)^* = r^*$, $r^* r^* = r^*$, $r r^* = r^* r$, $(r \mid \varepsilon)^* = r^*$, $(r \mid s)^* = (r^* s^*)^* = (r^* s)^* r^*$, and $(r s)^* r = r (s r)^*$ (the "sliding rule").

The table tests fifteen of the claims, each on a concrete choice (for instance $r = a$, $s = b$) by comparing the two languages on all strings up to length $7$. A row marked false has a witness string and is false in general; the standard true laws agree on all tested strings, and each is also a known theorem.

The popular false ones: $(r \mid s)^* \ne r^* \mid s^*$ (the left side contains $ab$, the right does not); $(rs)^* \ne r^* s^*$ (the left side is $\varepsilon, ab, abab, \ldots$, the right side contains $a$); $rs \ne sr$ (concatenation does not commute); and union does not distribute over concatenation: $r \mid s t \ne (r \mid s)(r \mid t)$ in general.

Writing expressions for the standard languages

Each expression below was compared with an independent predicate on every string of the stated alphabet up to length $10$.

Two techniques are behind most of these: a gap pattern $X^* \, \text{mark} \, X^*$ for "contains" and "at least", and a loop-and-exit pattern for "exactly $k$" or "divisible by $k$" (a block that contains one counted symbol, repeated).

Counting strings

The number of strings of length $n$ in $L(r)$ can be read off from the expression when it is unambiguous. $(a \mid b)^* a$ has $2^{n-1}$ strings of length $n$. The strings that contain $ab$ number $2^n - (n + 1)$ (the ones that do not contain $ab$ are $b^i a^j$, which are $n + 1$ of them). The language $(b \mid ab)^*$ has $1, 1, 2, 3, 5, 8, 13, 21$ strings of lengths $0, 1, 2, \ldots, 7$: each length is built from blocks $b$ (length $1$) and $ab$ (length $2$), and the counts follow the Fibonacci numbers. These counts were recomputed by brute force.

What regular expressions cannot say

A regular expression has a finite description with no counter, so languages such as $\{a^n b^n\}$ or the balanced parentheses have no regular expression (proved by the pumping lemma, pumping lemma). Programming-language "regex" engines add features such as backreferences that go beyond regular expressions (quoted, not verified here); this page speaks only about the theoretical operators.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Every regular expression has an equivalent NFA of linear size and every DFA an equivalent expression (regex and automata); scanner generators take token patterns written as regular expressions (lexical analysis); the design techniques for DFAs and expressions mirror each other (DFA design patterns).

PYQs

Consider the following two regular expressions over the
alphabet {0,1}:
r = 0* + 1*
s = 01* + 10*
The total number of strings of length less than or equal to
5, which are neither in r nor in s, is _________

Let L1 be the language represented by the regular expression
b *ab * (ab *ab * ) * and L2 = { w ∈ (a + b) * | |w| ≤ 4}, where
|w| denotes the length of string w. The number of strings in
L2 which are also in L1 is ___________

Which one of the following regular expressions represents
the set of all binary strings with an odd number of 1's?

Which one of the following regular expressions
represents the language: the set of all binary strings
having two consecutive 0s and two consecutive 1s?

The number of states in the minimal deterministic finite
automaton corresponding to the regular expression
 (0 + 1) * (10) is __________

The length of the shortest string NOT in the language (over
Σ = {a,b}) of the following regular expression is
a*b*(ba)*a* is ______________.

Consider the DFA given.

Which of the following are FALSE?
1. Complement of L(A) is context-free.
2. L(A) = L((11*0+0)(0 + 1)*0*1*)
3. For the language accepted by A, A is the minimal
DFA.
4. A accepts all strings over {0, 1} of length at least 2.

Let L = {w ∈ (0 + 1)* | w has even number of 1s}, i.e. L
is the set of all bit strings with even number of 1s. Which
one of the regular expression below represents L?

Self-check

Revision card

References