retagged by
21,031 views
51 votes
51 votes

A lexical analyzer uses the following patterns to recognize three tokens $T_1, T_2$, and $T_3$ over the alphabet $\{a, b, c\}$.

  • $T_1: a?(b \mid c)^\ast a$
  • $T_2: b?(a \mid c)^\ast b$
  • $T_3: c?(b \mid a)^\ast c$

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?

  1. $T_1T_2T_3$
  2. $T_1T_1T_3$
  3. $T_2T_1T_3$
  4. $T_3T_3$
retagged by

7 Answers

Best answer
54 votes
54 votes

Option D is the correct answer.

You can think $T_3$ as $\left ( \varepsilon + c \right )\left ( b+a \right )^{*}c$

Given string is $bbaacabc$

The longest matching prefix $\text{bbaac}$ { from regex $T3$ you can easily derive $\text{bbaac}$ }

Now the remaining  $\text{abc}$ { This can also be derived from $T3$ }

Hence $T3T3$ is the answer.

edited by
40 votes
40 votes
Option A
T1   T2    T3
bba  acab    bc

Option B
T1 T1 T3
bba aca bc

option C
T2 T1 T3
bb    aa  cabc

option D
T3         T3
bbaac      abc

all options can generate the string.

here option D has the longest prefix hence it is the answer.
10 votes
10 votes

option D is correct

bbaac -> this can be generated by T3 by taking c zero time, bbaa can be generated by (b+a)* and then append c at the end.

abc -> this can be again generated by taking T3

so the answer is T3T3

8 votes
8 votes

a? means either 0 or 1 occurrence of “a”, so we can write T1, T2 and T3 as:


T1 : (b+c)*a + a(b+c)*a
T2 : (a+c)*b + b(a+c)*b
T3 : (b+a)*c + c(b+a)*c


Now the string is: bbaacabc
Also given,
Token that matches the longest possible prefix
We can observe that the longest possible prefix in string is : bbaac which can be generated by T3.
After prefix we left with “abc” which is again generated by T3 (as longest possible prefix).


So, answer is T3T3.

Answer:

Related questions

19 votes
19 votes
4 answers
1
gatecse asked Feb 14, 2018
9,255 views
Consider the following parse tree for the expression a#b$\$$c$\$$d#e#f, involving two binary operators $\$$ and #.Which one of the following is correct for the given par...