Lexical Analysis Questions and Answers

Answer: C

Star binds tightest, then juxtaposition, then the vertical bar. This is why ab|c means the alternation of ab and c rather than a followed by the alternation of b and c. Parentheses are the only way to override the built in precedence of the operators.

Answer: D

Concatenation binds more tightly than alternation, so the expression groups as (ab)|c. Parentheses would be required to obtain a(b|c) instead. Getting this precedence wrong is one of the commonest mistakes in writing token patterns.

Answer: A

Correct answer: True

This is one half of Kleene’s theorem: every language denoted by a regular expression is accepted by some finite automaton, and conversely. Thompson’s construction gives the automaton mechanically, and the subset construction then makes it deterministic. The equivalence is what allows a scanner generator to turn a specification into a program.

Answer: B

Correct answer: a regular expression into a nondeterministic finite automaton

Thompson’s construction builds an NFA piece by piece from the structure of the expression, giving each operator - union, concatenation, closure - a small fixed pattern of states joined by epsilon transitions. The result is nondeterministic; the subset construction is the separate step that makes it deterministic, and minimisation a third.

Answer: C

Each state of the resulting DFA is a set of NFA states. The construction is what allows a scanner to run in time linear in the input despite the nondeterminism of the original automaton. The cost is paid once when the scanner is generated rather than on every input.

Answer: D

Each DFA state is a subset of the NFA states, so there are at most two to the power five, that is 32, of them including the empty set. In practice only the reachable subsets are constructed and the number is usually far smaller.

Answer: A

Both are true and the reason gives the mechanism, and the blow-up is rarely seen with real token definitions. Only reachable subsets are built, and the structure of typical lexical patterns keeps that number close to the size of the original automaton.

Answer: B

The pipeline moves from specification to NFA to DFA to a minimised table. Each step is mechanical, which is precisely why scanner generators can be trusted with the whole process. The author writes only the patterns and actions and never touches the automaton itself.

Answer: C

Correct answer: grouping states that cannot be distinguished by any input string

Two states are equivalent when no input string leads from one to acceptance and from the other to rejection, so nothing outside can tell them apart. Minimisation refines a partition until each block contains only mutually indistinguishable states and then collapses each block to a single state. Accepting and non-accepting states are distinguishable by the empty string and never merge.

Answer: D

Minimisation yields a canonical machine. This uniqueness is what makes it possible to test two regular expressions for equivalence by minimising both automata and comparing the results. No comparable canonical form exists for context free grammars, which is why equivalence there is undecidable.