Chapter 11 of 34

Regular Expressions

On this page

So far we have described languages in two ways: in plain English ("all strings that end with ab") and with machines (DFAs, NFAs, ε-NFAs). English is ambiguous, and a machine is a full diagram that takes time to read. What we often want is a short, precise formula for a language that you can write on one line.

That formula is a regular expression. You have probably used them already: grep, Python's re module, form validation and text editors all use regular expressions. In theory of computation we use a small, clean version with only three operations, and it turns out to describe exactly the languages that finite automata accept.

A regular expression is an algebraic description of a language, built from single symbols, ε and ∅ using three operations: union (+), concatenation and Kleene star (*).

In this chapter we define regular expressions formally, learn the precedence rules, translate between English and regular expressions with many solved problems, and learn the algebraic identities that GATE loves to test. Every regular expression in this chapter was checked by a program against its English description for all strings up to length 10.


Building Languages from Three Operations

Recall from Alphabets, Strings & Languages the three operations on languages:

  • Union: L1 ∪ L2 = strings in L1 or in L2.

  • Concatenation: L1L2 = { xy : x ∈ L1, y ∈ L2 }.

  • Kleene star: L* = L0 ∪ L1 ∪ L2 ∪ … = all strings formed by gluing together zero or more strings of L. Note that ε ∈ L* always.

A regular expression is simply a name for a language built with these operations, starting from the tiniest languages possible. Think of it like arithmetic: numbers and +, × let you write 2 × (3 + 4); symbols and +, ·, * let you write a(a + b)*.


Formal Definition

Let Σ be an alphabet. Regular expressions over Σ, and the language L(R) that each one denotes, are defined inductively:

Basis (the atoms):

Regular expression

Language it denotes

Meaning

∅

{ } (the empty set)

matches nothing at all

ε

{ ε }

matches only the empty string

a (for each a ∈ Σ)

{ a }

matches the one-symbol string a

Induction: if R1 and R2 are regular expressions, then so are:

Regular expression

Language

Read as

R1 + R2

L(R1) ∪ L(R2)

R1 or R2

R1R2

L(R1)L(R2)

R1 followed by R2

R1*

L(R1)*

zero or more R1's

(R1)

L(R1)

brackets, for grouping only

Nothing else is a regular expression. A language is called regular if some regular expression denotes it.

Two handy abbreviations (they add no power, they are just shorthand):

  • R+ = RR* = "one or more R's". So a+ = { a, aa, aaa, … }.

  • Rk = R written k times. So (a + b)3 = all strings of length exactly 3.

Notation warning. Many books (and programming languages) write union as | instead of +. In TOC, a + b means "a or b". In programming, a+ means "one or more a's", which TOC writes a+. Read the question carefully to see which convention is used.

∅ versus ε

This pair causes more lost marks than anything else in the chapter:

  • L(∅) = { } has no strings. L(ε) = { ε } has one string (of length 0).

  • Concatenating with ∅ kills everything: ∅R = R∅ = ∅ (there is no x ∈ ∅ to put in front).

  • Concatenating with ε changes nothing: εR = Rε = R.

  • Both stars are the same: ∅* = ε* = ε, because the star always contains ε (zero copies).


Precedence: How to Read a Regular Expression

Just as × binds tighter than + in arithmetic, regular expression operators have a fixed priority:

  1. Star (*) is applied first (highest).

  2. Then concatenation.

  3. Then union (+) (lowest).

Written

Means

Some strings in it

ab*

a(b*)

a, ab, abb, abbb

(ab)*

(ab)*

ε, ab, abab

a + bc

a + (bc)

a, bc

(a + b)c

(a + b)c

ac, bc

a + b*

a + (b*)

a, ε, b, bb

ab* + c

(a(b*)) + c

a, abb, c

So ab* is not "any number of ab"; the star sticks only to b. When in doubt, add brackets.


Reading Regular Expressions: What Language Is This?

Before writing regular expressions, practise reading them. The trick is to describe the shape of every string the expression can produce.

Regular expression (Σ = {a, b})

Language in English

(a + b)*

all strings, Σ*

a(a + b)*

strings that start with a

(a + b)*ab

strings that end with ab

(a + b)*aba(a + b)*

strings that contain aba as a substring

a*b*

some a's followed by some b's (no "ba" anywhere)

(a + b)(a + b)(a + b)

strings of length exactly 3 (8 strings)

(ε + a + b)3

strings of length at most 3 (15 strings)

((a + b)(a + b))*

strings of even length

(b + ab)*

every a is immediately followed by b

(a + ba)*

every b is immediately followed by a

How (b + ab)* works. Any string in it is a sequence of blocks, each block being b or ab. Every a appears only inside an "ab" block, so every a has a b right after it. Conversely, if every a is followed by b, you can cut the string into such blocks from left to right. So the language is "no aa and does not end with a".


Writing Regular Expressions: Solved Problems

Use Σ = {a, b} unless stated. The general strategy is: decide the fixed skeleton of the string, then fill the gaps with whatever is allowed there.

Problem 1: Exactly two a's

Skeleton: a … a. Before, between and after the two a's we may have only b's.

b* a b* a b*

Check: aa fits (all three b* empty), and babab fits as b·a·b·a·b. Strings of length 4 in this language: choose 2 of 4 positions for the a's = C(4, 2) = 6.

Problem 2: At least two a's

Skeleton: a … a, but now anything may appear around them.

(a + b)* a (a + b)* a (a + b)*      or, more compactly,    b* a b* a (a + b)*

The compact version pins down the first two a's: only b's can come before the first a and between the first two a's, then anything.

Problem 3: At most two a's

"At most two" means 0, 1 or 2. Make each a optional with (ε + a):

b* (ε + a) b* (ε + a) b*

Problem 4: Odd number of a's

Pin down the first a, then the remaining a's must come in pairs:

b* a b* (a b* a b*)*

After b*ab* we have seen exactly one a; each repetition of (ab*ab*) adds exactly two more, so the total stays odd. Every odd count 1, 3, 5, … is reachable.

Problem 5: No two consecutive a's

Every a except possibly a final one must be followed by b. Using the (b + ab)* idea and allowing an optional a at the end:

(b + ab)* (ε + a)

An equally correct answer is (ε + a)(b + ba)*. There are always many correct regular expressions for one language.

Problem 6: Starts and ends with the same symbol

Split into cases: length 1 (a or b), or longer with matching ends.

a (a + b)* a  +  b (a + b)* b  +  a  +  b

A very common wrong answer is a(a + b)*a + b(a + b)*b, which misses the single-symbol strings a and b (they start and end with the same symbol, but each needs at least two symbols in that expression).

Problem 7: Length divisible by 3

((a + b)(a + b)(a + b))*

Note that ε (length 0) is included, which is correct since 0 is divisible by 3.

Problem 8: Second symbol from the right is 1 (Σ = {0, 1})

(0 + 1)* 1 (0 + 1)

This one is famous because its regular expression is tiny but, as seen in Nondeterministic Finite Automata (NFA), its DFA needs more states (4 here, and 2n for "n-th from the right").

Problem 9 (harder): Even number of a's AND even number of b's

Think of reading the string two symbols at a time. A pair aa or bb keeps both counts' parity unchanged. A "mixed" pair (ab or ba) flips both parities, so we must later see another mixed pair to fix them, with any number of aa/bb pairs in between:

( aa + bb + (ab + ba)(aa + bb)*(ab + ba) )*

This expression was checked against the definition for all 2047 strings up to length 10. Strings of odd length are never accepted, as expected (even + even = even length).

Problem 10 (GATE favourite): Binary numbers divisible by 3 (Σ = {0, 1})

( 0 + 1 (0 1* 0)* 1 )*

We will derive this from the 3-state DFA in Finite Automata to Regular Expression (Arden's Theorem). For now, notice that it accepts ε as well (an empty string is usually treated as the number 0), and checks out for every binary string up to length 12.

Summary table of standard patterns

Language (Σ = {a, b})

Regular expression

starts with w

w(a + b)*

ends with w

(a + b)*w

contains w

(a + b)*w(a + b)*

length exactly n

(a + b)n

length at least n

(a + b)n(a + b)*

length at most n

(ε + a + b)n

length ≡ 0 (mod k)

((a + b)k)*

no "ba" (all a's before all b's)

a*b*

contains "ba"

(a + b)*b(a + b)*a(a + b)*, or (a + b)*ba(a + b)*


Algebraic Identities

Two regular expressions are equal (R = S) when they denote the same language. The following identities let you simplify expressions and are frequently tested. Here R, S, T are any regular expressions.

Identity

Why it holds

∅ + R = R

∅ adds no strings

∅R = R∅ = ∅

no string from ∅ to concatenate with

εR = Rε = R

ε is the identity for concatenation

R + R = R

union of a set with itself

R + S = S + R, (R + S) + T = R + (S + T)

union is commutative and associative

R(S + T) = RS + RT, (S + T)R = SR + TR

concatenation distributes over union

ε* = ε, ∅* = ε

star always contains ε, and nothing else here

(R*)* = R*

starring again adds nothing new

R*R* = R*

two blocks of R's are still a block of R's

RR* = R*R = R+

one or more R's

ε + RR* = ε + R*R = R*

"zero, or one or more" is "zero or more"

(ε + R)* = R*

picking ε contributes nothing

R(SR)* = (RS)*R

both are R S R S … R (the shifting rule)

(R + S)* = (R*S*)* = (R* + S*)* = (R*S)*R* = R*(SR*)*

all describe "any mix of R's and S's"

And two famous non-identities (the program found a counterexample for each):

Claim

Counterexample

(a + b)* = a* + b* ✗

ab is in the left side but not the right (right side has strings of only a's or only b's)

(ab)* = a*b* ✗

a is in a*b* but not in (ab)*; also abab is in (ab)* but not in a*b*

(R + S)* = R* + S* ✗ (in general)

same reason as the first row

(RS)* = R*S* ✗ (in general)

same reason as the second row

Worked example: simplifying

Simplify R = ε + 1*(011)*(1*(011)*)*.

Let P = 1*(011)*.        Then R = ε + P P*
ε + PP* = P*                                   (identity ε + RR* = R*)
So R = (1*(011)*)*
     = (1 + 011)*                              (identity (R*S*)* = (R + S)*)

The result: R describes all strings made of the blocks 1 and 011.

How to prove two expressions are NOT equal

Find one string in one language but not the other. Try short strings first: ε, then each single symbol, then length 2, and so on. To prove two expressions are equal, use identities, or convert both to minimal DFAs (see DFA Minimization) and compare.


Regular Expressions and Finite Automata

Here is the main theorem of this part of the course:

Kleene's Theorem: a language is denoted by some regular expression if and only if it is accepted by some finite automaton.

So "regular language" means the same thing whether you define it with regular expressions, DFAs, NFAs or ε-NFAs. The proof has two halves, each a chapter of its own:

  • Regular expression → ε-NFA: Regular Expression to Finite Automata (Thompson's construction).

  • Finite automaton → regular expression: Finite Automata to Regular Expression (Arden's Theorem).

This also tells you the limits of regular expressions. They cannot count without bound: there is no regular expression for { anbn : n ≥ 0 }, because no finite automaton can remember an unbounded n. (We prove this formally in Pumping Lemma for Regular Languages.) Writing a*b* does not help: it allows different numbers of a's and b's.

Practical regex vs. theory regex

Feature

TOC notation

Programming (POSIX / Python)

Union

a + b

a|b or [ab]

One or more

a+

a+

Optional

(ε + a)

a?

Any symbol

(a + b + …)

.

Back-references

not allowed

(a*)b\1 (matches anban, not regular!)

Everything in the programming column except back-references is just shorthand for a theory regex. Back-references go beyond regular languages, which is why matching them can be very slow in the worst case.

Check your answers with a few lines of Python

Python's re module can test a TOC-style expression if you replace + by |. This tiny brute-force checker is how the expressions in this chapter were verified:

import re, itertools

def check(toc_regex, definition, alphabet="ab", max_len=10):
    pattern = re.compile(toc_regex.replace(" ", "").replace("+", "|"))
    for n in range(max_len + 1):
        for t in itertools.product(alphabet, repeat=n):
            w = "".join(t)
            if bool(pattern.fullmatch(w)) != definition(w):
                return "mismatch on " + repr(w)
    return "OK"

print(check("b*ab*(ab*ab*)*", lambda w: w.count("a") % 2 == 1))
print(check("a(a+b)*a+b(a+b)*b", lambda w: len(w) > 0 and w[0] == w[-1]))

Output:

OK
mismatch on 'a'

The second line catches exactly the mistake from Problem 6: the string a is missing. (Brute force up to a length is a test, not a proof, but it catches nearly every slip.)


Common Mistakes

  • Confusing ∅ and ε. R∅ = ∅ but Rε = R. And ∅* = ε, not ∅.

  • Wrong precedence. ab* is a(b*), not (ab)*. a + b* is a + (b*).

  • Forgetting ε and short strings. Always test your expression on ε and on strings of length 1. "Starts and ends with the same symbol" must include a and b.

  • Using (a + b)* = a* + b*. The right side cannot mix a's and b's.

  • Distributing star over concatenation. (ab)* ≠ a*b*.

  • Reading + as "one or more". In TOC, a + b is union; one-or-more is a+.

  • Trying to count with a regex. anbn is not regular; a*b* is a different (larger) language.


GATE-Style Questions

Q1. Which of these is NOT equal to (a + b)*? (A) (a*b*)* (B) (a* + b*)* (C) a* + b* (D) (a*b)*a*

(C). a* + b* contains only strings of all a's or all b's, so ab is missing. (A), (B) and (D) are all standard forms of (a + b)*.

Q2. How many strings of length 5 are in L(b*ab*ab*)?

The language is "exactly two a's". Choose positions for the two a's among 5: C(5, 2) = 10.

Q3. What is the shortest string over {a, b} not in L((a + ba)*)?

The language is "every b is immediately followed by a". The string b fails (nothing follows it), so the answer is b (length 1). For the record, the strings of length 4 in the language are aaaa, aaba, abaa, baaa, baba: 5 of them.

Q4. Is (a + b)*ab(a + b)* equal to b*a*ab(a + b)*?

Yes. Both mean "contains ab". Look at the first occurrence of ab in a string: everything before it cannot contain ab, so it has the form b*a*. The right side just pins down that first occurrence.

Q5. Is a(ba)* equal to (ab)*a?

Yes, by the shifting rule R(SR)* = (RS)*R. Both are a, aba, ababa, … (alternating, starting and ending with a).

Q6. Which language does (0 + 1)*1(0 + 1) denote, and does every equivalent DFA need at least 4 states?

Binary strings whose second-last symbol is 1. Yes: the minimal DFA must remember the last two symbols (00, 01, 10, 11 behave differently), so it has 4 states.

Q7. Write a regular expression for strings over {a, b} in which the number of a's is divisible by 3.

(b*ab*ab*ab*)* b*, or equivalently b*(ab*ab*ab*)*. Each block contributes exactly three a's; leftover b's are absorbed by the b*'s. Note b* alone (zero a's) is included since 0 is divisible by 3.


Summary

  • Regular expressions are built from ∅, ε and single symbols using + (union), concatenation and * (Kleene star).

  • Precedence: star > concatenation > union. ab* = a(b*).

  • ∅R = ∅, εR = R, ∅* = ε* = ε.

  • Write regexes by fixing the skeleton of the string, then filling the gaps; always test ε and short strings.

  • Useful identities: R*R* = R*, (R*)* = R*, ε + RR* = R*, R(SR)* = (RS)*R, (R + S)* = (R*S*)*. Not identities: (R + S)* = R* + S*, (RS)* = R*S*.

  • By Kleene's theorem, regular expressions describe exactly the languages accepted by finite automata. The next two chapters give the constructions in both directions.