The expression ab|c denotes
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.
Please log in or register to report this question.
State whether the following is true or false.
Every regular expression describes a language that some finite automaton accepts.
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.
Please log in or register to report this question.
The Thompson construction converts
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.
Please log in or register to report this question.
The subset construction converts
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.
Please log in or register to report this question.
An NFA has 5 states. What is the maximum possible number of states in the DFA produced by the subset construction?
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.
Please log in or register to report this question.
Assertion (A): The subset construction can in the worst case produce exponentially many states.
Reason (R): Each state of the deterministic automaton corresponds to a subset of the states of the nondeterministic one.
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.
Please log in or register to report this question.
Arrange the steps of building a scanner from token specifications in the order they are performed.
1. convert it to a deterministic automaton by the subset construction
2. write a regular expression for each token
3. minimise the deterministic automaton and emit the table
4. build a nondeterministic automaton from the expressions
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.
Please log in or register to report this question.
DFA minimisation partitions the states by
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.
Please log in or register to report this question.
The minimal DFA for a regular language is
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.
Please log in or register to report this question.
Recognising the longest possible lexeme at each point is called
Answer: A
Without this rule the scanner would return a bare less than sign rather than the two character comparison operator at the start of an inequality. The scanner therefore continues while a longer lexeme remains possible and retreats to the last accepting position when it fails.
Please log in or register to report this question.
