GATE CS 2018 Q37 — Lexical Analysis

To find the sequence of tokens, we process the input string $S = \text{bbaacabc}$ from left to right, matching the longest possible prefix at each step.

Step 1: First Token Match

We analyze the prefixes of $S = \text{bbaacabc}$ starting from the left:

• b matches $T_2$ (since $b? = b$, $(a \mid c)^* = \epsilon$, ending with $b$).
• bb matches $T_2$ (since $b? = b$, $(a \mid c)^* = \epsilon$, ending with $b$).
• bba matches $T_1$ (since $a? = \epsilon$, $(b \mid c)^* = bb$, ending with $a$).
• bbaac matches $T_3$ (since $c? = \epsilon$, $(b \mid a)^* = bbaa$, ending with $c$).

No longer prefix matches any of the patterns because:

• bbaaca (ends in $a$) cannot match $T_1$ because $(b \mid c)^*$ cannot contain the internal $a$'s.
• bbaacab (ends in $b$) cannot match $T_2$ because $(a \mid c)^*$ cannot contain the internal $b$.
• bbaacabc (ends in $c$) cannot match $T_3$ because $(b \mid a)^*$ cannot contain the internal $c$.

Thus, the longest prefix matched is bbaac, which corresponds to token $T_3$.

Step 2: Second Token Match

The remaining string is $S' = \text{abc}$. We analyze its prefixes:

• a matches $T_1$ (since $a? = \epsilon$, $(b \mid c)^* = \epsilon$, ending with $a$).
• ab matches $T_2$ (since $b? = \epsilon$, $(a \mid c)^* = a$, ending with $b$).
• abc matches $T_3$ (since $c? = \epsilon$, $(b \mid a)^* = ab$, ending with $c$).

The longest prefix matched is the entire remaining string abc, which corresponds to token $T_3$.

Hence, the sequence of tokens output by the analyzer is $T_3T_3$.