CD Notes
Comprehensive guide to regular languages covering properties, closure operations, pumping lemma, decision problems, and applications in lexical analysis and token specification.
Introduction
Regular languages form the simplest class of languages in the Chomsky hierarchy and are the theoretical foundation for lexical analysis in compilers. Every token pattern — identifiers, keywords, numbers, operators — is described by a regular language. Understanding their properties helps compiler designers know exactly what can and cannot be accomplished at the scanning phase.
Definition and Equivalences
A language L is regular if and only if ANY of the following equivalent conditions holds:
- L is accepted by a DFA
- L is accepted by an NFA
- L is accepted by an ε-NFA
- L is described by a regular expression
- L is generated by a regular (right-linear) grammar
- L has a finite number of Myhill-Nerode equivalence classes
Regular Expressions
Regular expressions define regular languages using three basic operations:
Base cases
∅ → empty language {}
ε → language containing empty string {ε}
a → language containing single symbol {a}
Operations
R₁ | R₂ (Union) → L(R₁) ∪ L(R₂)
R₁ · R₂ (Concatenation) → L(R₁) · L(R₂)
R* (Kleene Star) → L(R)⁰ ∪ L(R)¹ ∪ L(R)² ∪ ...
Extended operators (syntactic sugar)
R+ = RR* (one or more)
R? = R | ε (zero or one)
[a-z] = a|b|c|...|z (character class)
. = any character (wildcard)
Precedence (highest to lowest)
1. * (Kleene star)
2. · (concatenation)
3. | (union)
Examples
Identifiers: [a-zA-Z_][a-zA-Z0-9_]*
Integers: [+-]?[0-9]+
Floats: [0-9]+\.[0-9]+(e[+-]?[0-9]+)?
Strings: \"[^\"]*\"
Regular Grammars
A regular grammar has productions of the form:
- Right-linear: A → aB | a | ε (where A, B are non-terminals, a is terminal)
- Left-linear: A → Ba | a | ε
| Example | Regular grammar for identifiers (letter followed by letters/digits) |
| S | aA | bA | ... | zA |
| A | aA | bA | ... | zA | 0A | 1A | ... | 9A | ε |
| Equivalent regex | [a-z][a-z0-9]* |
Closure Properties
Regular languages are closed under ALL major operations:
| Operation | Closed | Construction |
|---|---|---|
| Union (L₁ ∪ L₂) | Yes | Product construction / NFA |
| Intersection (L₁ ∩ L₂) | Yes | Product construction |
| Complement (L̄) | Yes | Swap final/non-final in DFA |
| Concatenation (L₁·L₂) | Yes | Connect NFA₁ end to NFA₂ |
| Kleene Star (L*) | Yes | Add loop in NFA |
| Difference (L₁ - L₂) | Yes | L₁ ∩ L̄₂ |
| Reversal (L^R) | Yes | Reverse all transitions |
| Homomorphism | Yes | Replace symbols |
| Inverse Homomorphism | Yes | Pre-image |
Closure Under Union (Proof Sketch)
| Product DFA | States = Q₁ × Q₂ |
| Final states for union | (q₁,q₂) where q₁∈F₁ OR q₂∈F₂ |
| Final states for intersection | q₁∈F₁ AND q₂∈F₂ |
Pumping Lemma for Regular Languages
Statement: If L is regular, there exists a pumping length p such that for any string w ∈ L with |w| ≥ p, w can be written as w = xyz where:
- |xy| ≤ p
- |y| ≥ 1
- For all i ≥ 0, xy^iz ∈ L
Using Pumping Lemma to prove L is NOT regular
Example: Prove L = {aⁿbⁿ | n ≥ 0} is not regular.
Proof by contradiction
1. Assume L is regular with pumping length p.
2. Choose w = aᵖbᵖ ∈ L (|w| = 2p ≥ p)
3. Write w = xyz where |xy| ≤ p, |y| ≥ 1
Since |xy| ≤ p, both x and y consist only of a's.
Let y = aᵏ for some k ≥ 1.
4. Pump with i = 0: xz = aᵖ⁻ᵏbᵖ
Since k ≥ 1, p-k < p, so aᵖ⁻ᵏbᵖ ∉ L
5. Contradiction! Therefore L is not regular.
Example: Prove L = {ww | w ∈ {a,b}*} is not regular.
1. Assume regular with pumping length p.
2. Choose w = aᵖbaᵖb ∈ L
3. xyz where |xy| ≤ p → y = aᵏ (only a's in first p positions)
4. Pump i=2: xy²z = aᵖ⁺ᵏbaᵖb ≠ uu for any u (unequal halves)
5. Contradiction → not regular.
Myhill-Nerode Theorem
Two strings x and y are indistinguishable with respect to L if for all strings z: xz ∈ L ↔ yz ∈ L.
| Theorem | L is regular ⟺ the number of equivalence classes |
| Example | L = {w ∈ {a,b}* | w contains "ab"} |
| 3 classes | minimal DFA has 3 states → L is regular. |
Decision Properties
| Problem | Decidable? | Algorithm | ||
|---|---|---|---|---|
| Membership (w ∈ L?) | Yes | Simulate DFA | ||
| Emptiness (L = ∅?) | Yes | Reachability | ||
| Finiteness ( | L | < ∞?) | Yes | Cycle detection |
| Equivalence (L₁ = L₂?) | Yes | Minimize & compare | ||
| Inclusion (L₁ ⊆ L₂?) | Yes | L₁∩L̄₂ = ∅? | ||
| Universality (L = Σ*?) | Yes | Check complement | ||
| Disjointness (L₁∩L₂ = ∅?) | Yes | Product DFA |
Applications in Compiler Lexical Analysis
Token Specification with Regular Expressions
Why Regular Languages Suffice for Tokens
Tokens in programming languages have these properties:
- Fixed keywords (finite set)
- Identifiers (letter followed by letters/digits — no nesting)
- Numbers (digit sequences with optional parts)
- Operators (fixed short strings)
- No recursive nesting needed at token level
Nested constructs (balanced braces, matched parens) are handled at the PARSING phase, not scanning.
Regular Language Operations in Lex/Flex
| x | character x |
| . | any character except newline |
| [xyz] | x, y, or z |
| [^xyz] | any character except x, y, z |
| [a-z] | a through z |
| r* | zero or more r |
| r+ | one or more r |
| r? | zero or one r |
| r{m,n} | m to n repetitions of r |
| r₁r₂ | r₁ followed by r₂ |
| r₁|r₂ | r₁ or r₂ |
| (r) | grouping |
| r₁/r₂ | r₁ when followed by r₂ (trailing context) |
| ^r | r at beginning of line |
| r$ | r at end of line |
Star-Free and Aperiodic Languages
A subset of regular languages that can be described without Kleene star (using only union, concatenation, and complement). These correspond to counter-free DFAs and are relevant for certain optimization analyses.
Interview Questions
- Q: Can a lexer detect unbalanced parentheses?
A: No. A lexer works with regular languages and cannot count nesting depth. It tokenizes "(" as LPAREN and ")" as RPAREN but cannot verify they are balanced. This check is performed by the parser (which uses a stack/PDA model).
- Q: Why do we need both regular expressions and context-free grammars?
A: Regular expressions handle flat token structure (no nesting needed). CFGs handle hierarchical program structure. Using CFGs for tokens would be wasteful; using regex for syntax would be impossible. The two-phase approach (scanner + parser) is both efficient and adequate.
- Q: How would you prove that the language of valid C programs is not regular?
A: C requires matching braces {} at arbitrary nesting depth. Consider strings "{ⁿ}ⁿ" — these must all be balanced. By the pumping lemma, we cannot pump within the opening braces without breaking the balance. Therefore, even this subset is non-regular, so valid C programs cannot form a regular language.
- Q: What is the relationship between DFA states and regular language equivalence classes?
A: The Myhill-Nerode theorem establishes a 1-to-1 correspondence between states of the minimal DFA and equivalence classes. Each state in the minimal DFA represents exactly one class of strings that are indistinguishable with respect to the language.
- **Q: Can regular expressions describe C-style comments /* ... */?**
A: Yes! Despite appearing to need "matching," C comments don't actually nest. The pattern is: /\*([^*]|\*+[^*/])*\*+/ — it matches from /* to the first */. This is regular because we just scan for the ending sequence without counting nesting depth.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Regular Languages in Compiler Design.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, automata, and, formal, languages
Related Compiler Design Topics