GATE CS 2018 Q.47 (CS Q.37): Lexical Analysis

A lexical analyzer uses the following patterns to recognize three tokens T1, T2, and T3 over the alphabet $\{a,b,c\}$ .

\begin{aligned} T_1 &: a? (b \mid c)^* a \\ T_2 &: b? (a \mid c)^* b \\ T_3 &: c? (b \mid a)^* c \end{aligned}

Note that ‘x?’ means 0 or 1 occurrence of the symbol x. Note also that the analyzer outputs the token that matches the longest possible prefix.

If the string $bbaacabc$ is processed by the analyzer, which one of the following is the sequence of tokens it outputs?

$T_1 T_2 T_3$

$T_1 T_1 T_3$

$T_2 T_1 T_3$

$T_3 T_3$

Official answer and solution

Solution

Trace the longest prefix matching mechanism on the input string against regular expressions $T_1$ , $T_2$ , and $T_3$ .

Given regular expression patterns:

$T_1: a? (b \mid c)^* a$ (ends with $a$ , preceded by $b$ or $c$ , optional initial $a$ )
$T_2: b? (a \mid c)^* b$ (ends with $b$ , preceded by $a$ or $c$ , optional initial $b$ )
$T_3: c? (b \mid a)^* c$ (ends with $c$ , preceded by $b$ or $a$ , optional initial $c$ )

Input string: $bbaacabc$

Step 1: Match longest prefix starting at position 0 (bbaacabc):

$T_1$ : Can match bba (length 3, since $a? = \varepsilon$ , $(b \mid c)^* = bb$ , then $a$ ). Next character is $a$ , which cannot extend $T_1$ .
$T_2$ : Can match bb (length 2, $b? = b$ , $(a \mid c)^* = \varepsilon$ , then $b$ ).
$T_3$ : Can match bbaac (length 5, $c? = \varepsilon$ , $(b \mid a)^* = bbaa$ , then $c$ ).
Comparing lengths, the longest prefix is bbaac of length 5, outputting token $T_3$ .

Step 2: Match remaining substring abc:

$T_1$ : Ends with $c$ , not $a$ , cannot match abc.
$T_2$ : Ends with $c$ , not $b$ , cannot match abc.
$T_3$ : For abc, $c? = \varepsilon$ , $(b \mid a)^* = ab$ , then $c$ . Matches entire string abc (length 3), outputting token $T_3$ .

Thus, the lexical analyzer outputs the sequence $T_3 T_3$ , matching option D.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.