Regular expressions (what lexical analysis needs)

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• How many prefixes does a string of length 7 have? from Lesson 0.2.1
• What is L* for a language L? from Lesson 0.2.1
• In which phase is the “words with their kinds” output produced? from Lesson 0.1.3

1 · The Story

📖

A card instead of an endless list

The Word Desk must recognise names of people and places in any speech. Nobody can list every possible name. Mira writes a pattern card instead: “a capital letter, then any number of small letters”. One card describes infinitely many words: Surat, Ramesh, Anand.

For amounts she writes “one or more digits”. For a price: “digits, then optionally a dot and two digits”. Each card is a short formula; any word that fits the card belongs to that kind.

Soon the cards build on each other: a card called digit, then a card amount that says “digit, one or more times”. Mira has invented a little language for describing languages.

2 · Predict First

🤔

Does the pattern “an a, then any number of b’s, written ab*” mean (ab) repeated, or a followed by repeated b’s? Write your guess down. The answer is in the vault.

3 · Core Concept

Building blocks

A regular expression r over Σ describes a language L(r). They are built from:

Precedence

Without brackets: star binds tightest, then concatenation, then |. So a | bc* means a | (b(c*)).

Shorthands

Regular definitions

Long expressions get names, and later names may use earlier ones (never themselves):

digit   → [0-9]
digits  → digit+
letter  → [A-Za-z_]
id      → letter ( letter | digit )*
number  → digits ( . digits )? ( E [+-]? digits )?

This is exactly how token kinds are described in Phase 1.

Useful identities

• r | s = s | r, and r | r = r
• (r*)* = r*, and ε* = ε
• (a | b)* = (ab)* : all strings over {a, b}
• r(s | t) = rs | rt

What they cannot do

A regular expression cannot describe “some opening brackets followed by the same number of closing brackets”: it cannot count without limit. Nested brackets need the more powerful tool of Phase 2. For the words of a program (names, numbers, operators) regular expressions are exactly enough.

Story → compiler term

4 · Visual

id = letter ( letter | digit )*: the first symbol must be a letter, then anything from letters and digits.

5 · Worked Examples

Example 1 Easy

Which of abb, aabb, abab, babb are in L((a|b)*abb)?

Solution

The expression means “anything over {a, b}, then exactly abb at the end”. abb ✔, aabb ✔ (prefix a), babb ✔ (prefix b), abab ✘ (ends in ab). Like checking a word against Mira’s card: only the ending is fixed here.

Example 2 Medium

Write a regular expression for unsigned decimal integers without leading zeros (0 is allowed).

Solution

0 | [1-9][0-9]*. Either the single word 0, or a non-zero digit followed by any digits. So 0, 7, 2027 match; 007 does not.

Example 3 GATE

How many strings of length 3 over {a, b} are in L((a|b)*a(a|b)), the strings whose second-last symbol is a?

Solution

Position 2 must be a; positions 1 and 3 are free: 2 × 2 = 4 strings (aaa, aab, baa, bab). Verified by checking all 8 strings of length 3.

6 · Shortcuts

⚡

Counting strings of length n that fix k positions: 2ⁿ⁻ᵏ over a 2-symbol alphabet (|Σ|ⁿ⁻ᵏ in general). Valid when: the fixed positions are fixed regardless of the rest (e.g. “ends in 00”, “second-last is a”).

⚡

Read star first, then concatenation, then |; add brackets mentally before deciding. Valid when: any unbracketed expression.

7 · GATE Traps

⚠️

• ab* is a(b*), not (ab)*.
• [0-9]+ does not match ε; [0-9]* does.
• (a|b)* already includes ε.
• A regular expression cannot match balanced brackets of unlimited depth.
• In a regular definition a name cannot refer to itself.

8 · Memory Hook

🧠

“Stars stick, neighbours join, bars choose.” * binds tightest, then concatenation, then |.

9 · Connect the Dots

Regular expressions describe the words. A program must also recognise them, reading characters one at a time. The machine that does that is the next primer.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markPrecedence

The regular expression a | bc* is equivalent to:

• (A) (a | b)c*
• (B) a | (b(c*))
• (C) (a | bc)*
• (D) a | (bc)*

Q2MSQ1 markEquivalence

Which regular expressions denote all strings over {a, b} (including ε)?

• (A) (a | b)*
• (B) (ab)*
• (C) ab
• (D) (a | b)(a | b)*

Q3NAT1 markCounting

How many strings of length 4 over {0, 1} are in L((0|1)*00)?

Numerical answer: ________

Q4NAT1 markCounting

How many strings of length 3 over {a, b} are in L(aba)?

Numerical answer: ________

Q5MCQ1 markLimits

Which language can not be described by a regular expression?

• (A) all strings over {a, b} ending in ab
• (B) all C identifiers
• (C) all strings of n opening brackets followed by n closing brackets, n ≥ 0
• (D) all unsigned integers

11 · Rule Card

• Building blocks: ε, a, r|s, rs, r*, (r).
• Precedence: * > concatenation > |.
• Shorthands: r+ = rr*, r? = r|ε, [a-z], [0-9].
• id → letter (letter | digit)*; number → digits (. digits)? (E [+-]? digits)?
• (a|b)* = (ab); (r)* = r*.
• Cannot count without limit (balanced brackets).

12 · Concept Ledger

regular expressionL(r)r|srsr*precedence * > · > |r+r?character class [a-z]regular definition

13 · Answer Vault