🔤 Lexical Analysis
Why it matters: Token-counting and DFA-state questions come up regularly; the regex → DFA pipeline is also asked in TOC.
Subtopics
Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 6 done.
1Tokens, lexemes and patterns
2Regular expression → NFA (Thompson)
3NFA → DFA (subset construction)
4DFA minimisation
5Maximal munch and rule priority
6Symbol table and lexical errors
Formulas
Thompson NFA size
states ≤ 2 × (#symbols + #operators); every state has at most 2 outgoing transitions
Subset construction worst case
n NFA states → up to 2^n DFA states
Minimal DFA
states = number of Myhill–Nerode equivalence classes (count the dead state only if the DFA must be complete)
Counting tokens
scan with maximal munch; each keyword, identifier, constant, operator, punctuation is one token; string literal = 1 token
What GATE asks from this
Question types seen repeatedly in past papers. More stars means more frequent.
★★★
Count the tokens in a code fragment
Apply maximal munch to a C snippet (e.g. with ++, ->, string literals, comments). Watch compound operators.
★★★
Minimal DFA states / DFA for a language
Convert a regex or NFA to a DFA and count states in the minimal DFA.
★★★
Role of the lexical analyser
What it outputs, what it does with whitespace/comments, why it is separate from the parser.
Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
2 real questions from the official GATE CSE papers (2018 to 2023), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
2 questions · 0 correct of 0 attempted · marks 0 / 3
Year:
GATE 2023 · Q19MCQ1 mark
Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions: letter → [A-Za-z]; digit → [0-9]; id → letter (letter | digit)*. Which one of the following Non-deterministic Finite-state Automata with ε-transitions accepts the set of valid identifiers? (A double circle denotes a final state.)
(A) start → letter → final state with a self-loop labelled letter/digit, plus an ε-edge from the first state straight to the final state. (B) start → letter → final state, with ε-edges to two further final states, one looping on letter and one looping on digit. (C) start → letter → final state; from the final state ε to a "letter" branch and ε to a "digit" branch, both ε-joined into a state that has an ε-edge back to the final state. (D) start → letter → final state; then letter → digit leading to a state with an ε-edge back to the final state.
(A) start → letter → final state with a self-loop labelled letter/digit, plus an ε-edge from the first state straight to the final state. (B) start → letter → final state, with ε-edges to two further final states, one looping on letter and one looping on digit. (C) start → letter → final state; from the final state ε to a "letter" branch and ε to a "digit" branch, both ε-joined into a state that has an ε-edge back to the final state. (D) start → letter → final state; then letter → digit leading to a state with an ε-edge back to the final state.
GATE 2018 · Q37MCQ2 marks
A lexical analyzer uses the following patterns to recognize three tokens T1, T2 and T3 over the alphabet {a, b, c}. T1: a? (b|c)* a T2: b? (a|c)* b T3: c? (b|a)* c. Note that "x?" means 0 or 1 occurrence of the symbol x. The analyzer outputs the token that matches the longest possible prefix. If the string bbaacabc is processed by the analyzer, which one of the following is the sequence of tokens it outputs?
Common traps
a+++b is a ++ + b under maximal munch.A comment or a string containing keywords is not extra tokens.
Subset construction needs ε-closure of the start state and after every move.