Lexical Analysis Practice Questions

The pumping lemma is used to prove that a language is NOT regular by showing no pumping length exists. In the context of lexical analysis: it explains why certain syntactic constructs cannot be handled at the lexical level. For example, balanced parentheses (the language {a^n b^n | n ≥ 1}) is not regular (pumping lemma proof: assume it's regular with pumping length p; take s = a^p b^p; any split xyz with |xy| ≤ p has y = a^k for some k ≥ 1; pumping gives a^(p+k) b^p ∉ L - contradiction). This is why compilers use CFGs and parsers for syntactic structure and use regular expressions/DFAs only for tokenization (which deals with flat, non-nested patterns).

The DFA for (a|b)*abb (strings ending in 'abb') has 4 states: State A (initial): no progress toward 'abb' - transitions: on a→B, on b→A. State B: seen 'a' (potential start of 'abb') - transitions: on a→B (reset with new 'a'), on b→C. State C: seen 'ab' - transitions: on a→B, on b→D. State D (accepting): seen 'abb' - transitions: on a→B, on b→A. After minimization: these 4 states are all distinguishable (they accept different sets of future strings), so the minimal DFA has 4 states. This is a classic GATE example from Aho-Lam-Sethi-Ullman textbook.

The standard construction pipeline for a lexical analyzer: (1) Regular expression → NFA: Thompson's construction algorithm converts a regular expression to an ε-NFA in O(|r|) time with O(|r|) states. (2) NFA → DFA: Subset (powerset) construction converts the NFA to an equivalent DFA. Each DFA state corresponds to a set of NFA states. May produce up to 2^n DFA states for n NFA states (worst case). (3) DFA minimization: Hopcroft's algorithm minimizes the DFA by merging indistinguishable states. The minimized DFA is the basis for the lexer's finite automaton. Tools like lex/flex implement this pipeline automatically.

The lexical analyzer (scanner/lexer) is the first phase of a compiler. It reads the source program as a stream of characters and groups them into tokens - meaningful units such as keywords (if, while), identifiers (variable names), operators (+, ==), literals (42, 3.14, 'hello'), and punctuation ({, ;). It skips whitespace and comments, which are not tokens. The output is a sequence of tokens passed to the parser. It may also interact with the symbol table to record identifier attributes. Syntax checking is the parser's job; IR generation is the semantic analyzer's/code generator's job.

Minimum DFA for C-style /* ... / comments: State 0 (initial): waiting for '/'. On '/'→State 1, else→State 0. State 1: seen '/'. On ''→State 2 (inside comment), on '/'→State 1, else→State 0. State 2: inside comment body. On ''→State 3 (potential end), else→State 2. State 3: seen '' inside comment (potential '/'). On '/'→State 4 (accept: comment closed), on '*'→State 3, else→State 2. State 4 (accepting): comment complete. Total = 5 states (0,1,2,3,4). These are all distinguishable: State 2 and 3 differ (State 3 transitions to accept on '/', State 2 does not). Minimum = 5 states.

A token is a pair: (token-type, attribute-value). The token type (name) is an abstract category: id, number, relop, keyword, etc. The attribute value provides additional information when multiple lexemes map to the same token type. Example: the identifier 'count' → token (id, pointer to symbol table entry for 'count'). The number '3.14' → token (number, 3.14). The keyword 'if' → token (if, -) - no attribute needed since there is only one 'if'. The lexeme is the actual character string matched, not the token itself. The token is the abstract representation passed to the parser.

DFA vs NFA: A: TRUE - both DFAs and NFAs recognize exactly the class of regular languages. Every NFA can be converted to an equivalent DFA (subset construction) and vice versa. B: TRUE - in an NFA, from state s on input a, there may be zero, one, or multiple possible next states. In a DFA, there is exactly one next state for each (state, input) pair (the transition function is total and deterministic). C: TRUE - NFAs may have ε-transitions (move without consuming input); DFAs cannot (every transition must consume exactly one input symbol). D: FALSE - DFAs and NFAs are equally expressive (both characterize regular languages). The difference is in conciseness: an NFA may be exponentially more succinct than the equivalent DFA.

L(r) = L(a(a|b)b) = all strings starting with 'a' and ending with 'b' over {a,b}, with zero or more characters in between. A: 'ab' - 'a' matches first 'a', (a|b) matches ε, 'b' matches last 'b'. Accepted ✓. B: 'aab' - 'a' matches first 'a', (a|b)* matches 'a', 'b' matches last 'b'. Accepted ✓. C: 'abb' - 'a' matches first 'a', (a|b)* matches 'b', 'b' matches last 'b'. Accepted ✓. D: 'ba' - starts with 'b' not 'a', and ends with 'a' not 'b'. Rejected ✗. Note: strings like 'aaa' (ends with 'a') and 'bab' (starts with 'b') are also not in L(r).

Two DFA states p and q are distinguishable if there exists a string w (a distinguishing string) such that: starting from p, w leads to an accepting state, but starting from q, w leads to a non-accepting state (or vice versa). In other words, δ*(p,w) ∈ F XOR δ*(q,w) ∈ F. Indistinguishable states can be merged. Table-filling algorithm (marking algorithm): initialize by marking all (accepting, non-accepting) pairs as distinguishable. Iteratively mark (p,q) if for some input a, (δ(p,a), δ(q,a)) is already marked. Unmarked pairs at termination are indistinguishable and can be merged.

Three related but distinct concepts: Pattern: a rule (regular expression) describing the set of strings that can form a token of a given type. Example: pattern for identifiers = letter(letter|digit)*. Lexeme: the actual sequence of characters in the source program that matches a pattern. Example: 'count', 'x1', 'myVariable'. Token: the abstract pair (token-type, attribute-value) produced by the lexer when a lexeme matches a pattern. Example: (id, pointer-to-count-in-symbol-table). Multiple lexemes match the same pattern; each lexeme produces a token instance. The parser works with tokens; the lexer works with lexemes and patterns.

Thompson's construction for (a|b): Step 1 - NFA for 'a': 2 states (states 0, 1). Step 2 - NFA for 'b': 2 states (states 2, 3). Step 3 - NFA for (a|b) using alternation: add new start state 4 and new final state 5, with ε-transitions 4→0, 4→2, 1→5, 3→5. Total: 6 states (0,1,2,3,4,5). Step 4 - NFA for (a|b) using Kleene star: add new start state 6 and new final state 7, with ε-transitions: 6→4 (enter the body), 5→4 (loop back), 5→7 (exit), 6→7 (match empty string). Total: 8 states (0-7). Thompson's construction for r* always adds exactly 2 states to NFA_r.

L = strings where the count of 0s is divisible by 3 (0, 3, 6, 9, ... zeros). The DFA needs to count the number of 0s modulo 3: State q0 (initial, accepting): count of 0s ≡ 0 (mod 3). On 0→q1, on 1→q0. State q1: count ≡ 1 (mod 3). On 0→q2, on 1→q1. State q2: count ≡ 2 (mod 3). On 0→q0, on 1→q2. All three states are distinguishable: from q0, ε is accepted; from q1, '00' is accepted (total 3 zeros); from q2, '0' is accepted (total 3 zeros - 2+1). Minimum DFA has 3 states. Input 1s don't change the count, so on 1 we stay in the same state.

Lex/Flex operation: (1) Input: a .l file containing regular expression patterns paired with actions (C code). (2) Processing: lex combines all patterns into a single regular expression using alternation, converts it to an NFA using Thompson's construction, converts the NFA to a DFA using subset construction, and minimizes the DFA. (3) Output: C code (lex.yy.c) implementing the DFA as a large switch statement or table-driven scanner. The generated scanner reads input, simulates the DFA, applies the longest-match and priority rules, and executes the action for each matched token. The result is a compiled, efficient table-driven DFA scanner.

Regular language properties: A: TRUE - closure under union (r|s), concatenation (rs), and Kleene star (r*). Also closed under intersection, complement, difference, and reversal. B: TRUE - Kleene's theorem: a language is regular iff it is described by a regular expression iff it is accepted by some DFA/NFA. C: FALSE - regular languages CANNOT describe nested/recursive structures. Balanced parentheses requires counting (stack), which finite automata cannot do. This is provable by the Pumping Lemma for regular languages. This is why parsers (using CFGs/PDAs) are needed for syntax - the syntactic structure of programs is context-free, not regular. D: TRUE - regular languages are closed under intersection.

Lexical analysis tasks: A: TRUE - whitespace and comments are not tokens; the lexer discards them (or optionally passes them to the parser as special tokens for formatting tools). B: TRUE - the core lexer function: pattern matching to categorize character sequences into token types. C: FALSE - checking balanced parentheses requires counting/stack memory, which is beyond regular languages. This is a syntactic task for the parser (context-free grammar / pushdown automaton). D: FALSE - in C, the preprocessor (cpp) is a separate phase that runs BEFORE lexical analysis: it expands macros (#define), handles #include, #if/#ifdef, etc. The lexer processes the preprocessor output. Some compilers integrate preprocessing, but it is conceptually a separate phase.

Lexical errors (detectable by the lexer): A: TRUE - if the lexer encounters a character that does not match the beginning of any valid token pattern, it reports a lexical error (illegal character). Example: '$' in standard C is not valid. B: TRUE - an unterminated string literal (no closing quote before end of line or file) cannot match the string token pattern and is a lexical error. The lexer can detect this by recognizing it reaches EOF while still in the 'inside string' state. C: FALSE - using an undeclared variable is a semantic error (detected during semantic analysis when the symbol table is consulted for types). D: FALSE - missing semicolons are syntax errors detected by the parser, not the lexer (the lexer just produces tokens; it doesn't check their grammatical structure).

The set of strings over {a,b} containing at least one 'a': There must be at least one 'a' somewhere in the string, with any combination of 'a' and 'b' before and after it. Option A: (a|b)* a (a|b)* - zero or more (a or b), then an 'a', then zero or more (a or b). This correctly accepts any string with at least one 'a'. Option B: a* - only strings of all 'a's (no b's allowed). Option C: (a|b)+ - strings of length ≥ 1 over {a,b}; includes 'b', 'bb', etc. which contain no 'a'. Option D: b* a (a|b)* - correct but incomplete; requires all characters before the first 'a' to be 'b's, which is actually equivalent to A. Actually D is equivalent to A. Both A and D are correct.

ε-closure(s) is the set of all NFA states reachable from state s using zero or more ε-transitions (without consuming any input symbol). s itself is always in ε-closure(s). Algorithm: start with {s}, repeatedly add any state reachable via ε from any state in the current set, until no new states can be added. ε-closure is used in subset construction: the initial DFA state = ε-closure(NFA initial state). For DFA state D and input symbol a: MOVE(D, a) = set of NFA states reachable from any state in D on input a; new DFA state = ε-closure(MOVE(D, a)).

An identifier in most languages (C, Java, Python) must begin with a letter (or underscore) followed by zero or more letters or digits. The regular expression is: (letter)(letter | digit)* where letter = [a-zA-Z_] and digit = [0-9]. Option B allows identifiers to start with digits (invalid). Option C requires identifiers to start with a digit (incorrect - those are numeric literals). Option D requires identifiers to contain only letters (no digits allowed - too restrictive). Option A correctly captures: first character must be a letter, subsequent characters can be letters or digits.