Lexical Analysis Questions and Answers

Answer: A

Correct answer: a distinguished end of file token returned by the scanner

The parser needs to know that the input has ended in the same form as everything else it consumes, so the scanner returns a special end of file token, conventionally written as a dollar sign in grammars. The grammar then has a production that accepts the start symbol followed by that token, which is how it recognises a complete program.

Answer: B

Equivalence is about the language denoted, not the notation. Minimising the deterministic automata of both and comparing them decides equivalence, since the minimal machine is canonical. Two expressions that look nothing alike may well denote exactly the same language.

Answer: C

Both generate every string over the two letters, including the empty one. This pair is the standard illustration that very differently written expressions can denote the same regular language. Only minimisation of the corresponding automata settles the question conclusively.

Answer: D

Correct answer: always regular, obtained by swapping accepting and non-accepting states

Take a complete deterministic automaton for the language and exchange its accepting and non-accepting states: the resulting machine accepts exactly the strings the original rejected. The construction requires the automaton to be deterministic and complete, with a transition defined for every state and character, which is why a dead state is added first if one is missing.

Answer: A

Correct answer: the product automaton formed from the two deterministic machines

The product automaton has one state for each pair of states of the two originals and runs them side by side on the same input, accepting only when both would accept. Making the accepting condition “either” instead of “both” gives the union by the same construction, which is one way of showing regular languages closed under both.

Answer: B

Correct answer: All of them

Regular languages are closed under all three, and under intersection and difference besides. Union and concatenation follow directly from the regular expression operators; complementation follows from swapping accepting and non-accepting states of a complete DFA; and intersection then follows from the other two by De Morgan, or directly from the product construction.

Answer: C

Merging the patterns into one machine means the input is scanned once rather than once per token. The accepting state reached identifies which pattern matched, and rule order breaks any tie. One pass over the input therefore suffices no matter how many tokens are defined.

Answer: D

Correct answer: the specification is short, declarative and easy to change

A Lex specification states what the tokens look like and leaves the construction of the automaton to the tool, so it is a fraction of the length of the equivalent code and can be changed by editing one pattern. A carefully hand-written scanner can be faster, so speed is not the argument; maintainability is.

Answer: A

Correct answer: the language has unusual rules that patterns express awkwardly

Hand writing is chosen where the lexical structure does not fit the regular expression model comfortably - significant indentation, nested comments, string interpolation, or context-dependent rules such as Fortran’s insignificant blanks. Writing the awkward parts directly is often clearer than forcing them into patterns with elaborate actions and start conditions.

Answer: D

The analyzer outputs \(T_{3}T_{3}\).

It always takes the longest prefix any pattern matches. On bbaacabc:

• \(T_{1}\) can match bba (no leading a, then bb, then a): 3 characters.
• \(T_{2}\) can match only bb, since \((a|c)^{*}\) cannot absorb the second b: 2 characters.
• \(T_{3}\) can match bbaac (no leading c, then bbaa from \((b|a)^{*}\), then c): 5 characters.

So the first token is \(T_{3}\), for bbaac. The rest is abc: \(T_{3}\) matches all of it (ab, then c), while \(T_{1}\) matches only a and \(T_{2}\) only ab. So the second token is \(T_{3}\) too.

The options starting with \(T_{1}\) or \(T_{2}\) take a shorter prefix than the longest-match rule allows.