CD Notes

Finite Automata in Lexical Analysis

How finite automata (DFA and NFA) are used in lexical analysis to implement pattern matching for token recognition in compilers.

Introduction

Finite automata are the computational model underlying lexical analysis. Every regular expression (used to define token patterns) can be converted into a finite automaton that recognizes exactly the same set of strings. The lexical analyzer is essentially a collection of finite automata running in parallel, each trying to match a different token pattern.

Types of Finite Automata

Nondeterministic Finite Automaton (NFA)

An NFA is defined as a 5-tuple: N = (Q, Σ, δ, q₀, F) where:

Q = finite set of states
Σ = input alphabet
δ = transition function: Q × (Σ ∪ {ε}) → P(Q)
q₀ = start state
F = set of accepting (final) states

NFAs can have:

Multiple transitions on the same input from a state
ε-transitions (transitions without consuming input)

Deterministic Finite Automaton (DFA)

A DFA is defined as a 5-tuple: D = (Q, Σ, δ, q₀, F) where:

δ = transition function: Q × Σ → Q (exactly one transition per input)
No ε-transitions allowed
Exactly one next state for each state-input pair

NFA for Token Recognition

Thompson's Construction

Every regular expression can be converted to an NFA using Thompson's construction:

Base cases:

Example

For symbol 'a': For ε: ─→(i)─a─→((f)) ─→(i)─ε─→((f))

Concatenation (rs):

Example

─→(i₁)─[NFA for r]─→(f₁)─ε─→(i₂)─[NFA for s]─→((f₂))

Alternation (r|s):

Example

ε ┌─[NFA for r]─┐ ε ─→(i)─┤ │ │──→((f)) ε └─[NFA for s]─┘ ε

**Kleene Closure (r*):**

Example

ε ┌─────────────────────┐ │ ε │ ε ─→(i)──┼──→[NFA for r]──→(m)─┼──→((f)) │ │ └──────────────────────┘ ε (direct from i to f)

Example: NFA for (a|b)*abb

ε ┌─a─	3 ─ε─┐ ε
─	0 ─ε─→ 1 ──┤ ├──→ 2 ─ε─→ 1 (loop back)
└─b─	4 ─ε─┘ │
5 ─a─	6 ─b─→ 7 ─b─→ ((8))

Subset Construction: NFA to DFA

The subset construction algorithm converts an NFA to an equivalent DFA:

Algorithm

Example

1. Start state of DFA = ε-closure({q₀}) 2. For each unmarked DFA state T: a. Mark T b. For each input symbol a: U = ε-closure(move(T, a)) If U is not in DFA states, add it Add transition T --a--> U 3. DFA accepting states = all states containing an NFA accepting state

Example: Converting (a|b)*abb NFA to DFA

From A on 'a'	move(A,a) = {3,6}
From A on 'b'	move(A,b) = {4}
From B on 'a':	State B
From B on 'b':	{1,2,3,4,5,7} = State D
From C on 'a':	State B
From C on 'b':	State C
From D on 'a':	State B
From D on 'b':	{1,2,3,4,5,8} = State E (accepting!)
From E on 'a':	State B
From E on 'b':	State C

Resulting DFA:

Example

a b a b →[A] ──→ [B] ──→ [D] ──→ [B] │ ↑ │ b a b ▼ │ ▼ [C] ─────┘ [[E]] (accepting) ↑ │ └───────b───────┘

DFA Minimization

Minimize the DFA by merging equivalent states:

Hopcroft's Algorithm

Example

1. Partition states into accepting and non-accepting groups 2. Refine partitions: split groups where states have transitions to different groups on some input 3. Repeat until no more splits possible 4. Each final partition group becomes one DFA state

Implementation in Lexical Analyzer

Table-Driven DFA

Example

int transition_table[NUM_STATES][ALPHABET_SIZE] = { /* State 0 */ {1, 2, -1, ...}, // transitions on 'a','b',... /* State 1 */ {1, 3, -1, ...}, /* State 2 */ {1, 2, -1, ...}, /* State 3 */ {1, 4, -1, ...}, /* State 4 */ {1, 2, -1, ...}, // accepting state }; int accepting[] = {0, 0, 0, 0, 1}; // State 4 is accepting Token scan() { int state = 0; int last_accepting = -1; int last_accepting_pos = -1; while (state != -1) { char c = next_char(); state = transition_table[state][c]; if (accepting[state]) { last_accepting = state; last_accepting_pos = current_pos; } } // Return to last accepting position retract_to(last_accepting_pos); return make_token(last_accepting); }

Multiple Pattern Matching

In practice, the lexical analyzer combines multiple token patterns into a single DFA:

ε	[NFA for identifiers] → accept(ID)
ε	[NFA for numbers] → accept(NUM)
ε	[NFA for operators] → accept(OP)
ε	[NFA for keywords] → accept(KW)

Then convert to a single DFA where each accepting state knows which token it represents.

Comparison: NFA vs DFA for Lexical Analysis

Aspect	NFA	DFA
Construction	Easier from regex	Requires subset construction
Size	O(n) states for regex of length n	Can be O(2^n) states (worst case)
Matching speed	Slower (multiple paths)	O(1) per character (single path)
Implementation	Simulation needed	Direct table lookup
Used in practice	Intermediate step	Final implementation

Interview Questions

Why are finite automata used in lexical analysis?

Because every regular expression (which defines token patterns) has an equivalent finite automaton. DFAs provide O(1) per-character matching speed, making them ideal for efficient token recognition in compilers.

What is the difference between NFA and DFA in the context of lexical analysis?

An NFA can have multiple transitions on the same input and ε-transitions, making it easier to construct from regex but harder to simulate. A DFA has exactly one transition per input, enabling direct O(1) lookups but potentially exponential state count.

Explain Thompson's construction.

Thompson's construction converts a regular expression to an NFA by building small NFAs for base cases (single characters, ε) and combining them using rules for concatenation, alternation, and Kleene closure. Each operation adds at most 2 new states.

What is the subset construction algorithm?

It converts an NFA to a DFA where each DFA state represents a set of NFA states. Starting from ε-closure of the start state, it computes transitions by finding ε-closures of move sets. DFA accepting states are those containing any NFA accepting state.

How does a lexical analyzer handle multiple token patterns simultaneously?

All token patterns are combined into a single NFA (with ε-transitions from a new start state to each pattern's NFA), then converted to one DFA. Each accepting state records which token pattern it matches. The longest match and priority rules resolve conflicts.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Finite Automata in Lexical Analysis.

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, lexical, analysis, finite, automata

Continue learning this concept

Lexical AnalysisIntroduction to Lexical AnalysisComprehensive introduction to lexical analysis, the first phase of a compiler that reads source code and produces tokens for the parser.Lexical AnalysisLex Tool - Lexical Analyzer GeneratorComplete guide to the Lex tool for automatic generation of lexical analyzers from regular expression specifications, including syntax, rules, and examples.Lexical AnalysisLexemes in Compiler DesignUnderstanding lexemes, their role in lexical analysis, how they are identified from source code, and their relationship with tokens and patterns.Lexical AnalysisLexical Analyzer DesignComplete guide to designing and implementing a lexical analyzer including architecture, algorithms, buffering strategies, and practical implementation.Lexical AnalysisLexical Errors and Error RecoveryUnderstanding lexical errors in compiler design, types of errors detected during scanning, and error recovery strategies used by lexical analyzers.Lexical AnalysisPatterns in Lexical AnalysisUnderstanding patterns that define valid lexemes for each token type, pattern specification using regular expressions, and pattern matching in scanners.

PreviousThe Preprocessor NextIntroduction to Lexical Analysis

CD Notes

Finite Automata in Lexical Analysis

How finite automata (DFA and NFA) are used in lexical analysis to implement pattern matching for token recognition in compilers.

Introduction

Types of Finite Automata

Nondeterministic Finite Automaton (NFA)

An NFA is defined as a 5-tuple: N = (Q, Σ, δ, q₀, F) where:

Q = finite set of states
Σ = input alphabet
δ = transition function: Q × (Σ ∪ {ε}) → P(Q)
q₀ = start state
F = set of accepting (final) states

NFAs can have:

Multiple transitions on the same input from a state
ε-transitions (transitions without consuming input)

Deterministic Finite Automaton (DFA)

A DFA is defined as a 5-tuple: D = (Q, Σ, δ, q₀, F) where:

δ = transition function: Q × Σ → Q (exactly one transition per input)
No ε-transitions allowed
Exactly one next state for each state-input pair

NFA for Token Recognition

Thompson's Construction

Every regular expression can be converted to an NFA using Thompson's construction:

Base cases:

Example

For symbol 'a': For ε: ─→(i)─a─→((f)) ─→(i)─ε─→((f))

Concatenation (rs):

Example

─→(i₁)─[NFA for r]─→(f₁)─ε─→(i₂)─[NFA for s]─→((f₂))

Alternation (r|s):

Example

ε ┌─[NFA for r]─┐ ε ─→(i)─┤ │ │──→((f)) ε └─[NFA for s]─┘ ε

**Kleene Closure (r*):**

Example

Example: NFA for (a|b)*abb

ε ┌─a─	3 ─ε─┐ ε
─	0 ─ε─→ 1 ──┤ ├──→ 2 ─ε─→ 1 (loop back)
└─b─	4 ─ε─┘ │
5 ─a─	6 ─b─→ 7 ─b─→ ((8))

Subset Construction: NFA to DFA

The subset construction algorithm converts an NFA to an equivalent DFA:

Algorithm

Example

Example: Converting (a|b)*abb NFA to DFA

From A on 'a'	move(A,a) = {3,6}
From A on 'b'	move(A,b) = {4}
From B on 'a':	State B
From B on 'b':	{1,2,3,4,5,7} = State D
From C on 'a':	State B
From C on 'b':	State C
From D on 'a':	State B
From D on 'b':	{1,2,3,4,5,8} = State E (accepting!)
From E on 'a':	State B
From E on 'b':	State C

Resulting DFA:

Example

a b a b →[A] ──→ [B] ──→ [D] ──→ [B] │ ↑ │ b a b ▼ │ ▼ [C] ─────┘ [[E]] (accepting) ↑ │ └───────b───────┘

DFA Minimization

Minimize the DFA by merging equivalent states:

Hopcroft's Algorithm

Example

Implementation in Lexical Analyzer

Table-Driven DFA

Example

Multiple Pattern Matching

In practice, the lexical analyzer combines multiple token patterns into a single DFA:

ε	[NFA for identifiers] → accept(ID)
ε	[NFA for numbers] → accept(NUM)
ε	[NFA for operators] → accept(OP)
ε	[NFA for keywords] → accept(KW)

Then convert to a single DFA where each accepting state knows which token it represents.

Comparison: NFA vs DFA for Lexical Analysis

Aspect	NFA	DFA
Construction	Easier from regex	Requires subset construction
Size	O(n) states for regex of length n	Can be O(2^n) states (worst case)
Matching speed	Slower (multiple paths)	O(1) per character (single path)
Implementation	Simulation needed	Direct table lookup
Used in practice	Intermediate step	Final implementation

Interview Questions

Why are finite automata used in lexical analysis?

What is the difference between NFA and DFA in the context of lexical analysis?

Explain Thompson's construction.

What is the subset construction algorithm?

How does a lexical analyzer handle multiple token patterns simultaneously?

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Finite Automata in Lexical Analysis.

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, lexical, analysis, finite, automata

Continue learning this concept

PreviousThe Preprocessor NextIntroduction to Lexical Analysis