GATE CSE 2018 | Question: 37

Question

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?

• A. $T_1T_2T_3$
• B. $T_1T_1T_3$
• C. $T_2T_1T_3$
• D. $T_3T_3$

Comments

No, it is not. T1 contains all strings ending with a.

---

It is not any new terminology devised for this question. ? is a standard symbol used for the same purpose, according to Hopcroft.

---

@LRU

Thanks for correcting.

Yup last a we have to take. I don’t know why i misread as a*.

Answer 1

The answer is T₃T₃ as the question specifically mentioned that it will prefer the relational algebra which generates the longest subsequence.

With  T₃ you get a subsequence of 5, whereas with T₂ you get a subsequence of only 3.

Hence, T₃ preferred over T₂.

So option D is the correct answer.

Comments

How did you get subsequence of 3 from T2? i am getting only "bb' which is subsequence of 2.

Answer 2

Answer D T3T3

Answer can also be B,C if this line is not given.

Note also that the analyzer outputs the token that matches the longest possible prefix.

B T1T1T3

Which generates bba aca bc 

C T2T1T3.

bb aa cabc 

D T3T3

bbaac abc 

here longest prefix length is 5

 

Answer 3

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
Please NOTE:
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.