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

Marked D as well

---

d  how????

---

correct.

---

d option

---

I also got T₃T₃, as the question specifically mentioned that it will prefer the relational algebra which generates the longest subsequence.

---

t3t3 is answer

---

I think b option is also correct try to pardeparse the string using t1t1t3 it works fine. .  Seems to be ambigous question. .

---

longest possible prefix matched with the string is "bbaac" generated by T3 and then "abc" by T3, so T3T3 is the answer.

---

what is meant  by ? in regex

---

@sushmita ? is new terminology defined in the question as only 0 or 1 occurrence of a symbol.

---

lets generate the regular expression of each .

x = denotes 0 or 1 occurence of symbol x. So either it will be epsilon or 1 .

String to be generated :- bbaacabc

The regular expressions :-

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

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

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

lets see which regular expression generations the longest possible prefix

String = bbaacabc

T1 : bba

T2 : bb

T3 : bbaac

So , as we can see T3 is generating the longest possible prefix here

Now , again in the string (abc) also need to be generated  , lets check which regular expression generates (abc).

T1 : end with a , but we want to end with c – so abc not possible

T2 : end with b , but we want to end with c – so abc not possible

T3:- (b + a ) * c – ending with c and also b and a can be generated inside the closure – so , yes T3 can generate abc.

Therefore total string (bbaacabc) is generated using T3T3.

So, Answer is option (D) T3T3

---

Anyone confirm this...

T3T1 is also possible answer if given in options.

---

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

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.

Comments

Here, T1 : (b+c)* a + a(b+c)* a

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

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

So,if we take T3 then if we want to generate "bbaac" i.e the longest prefix then if we take first option of T3 i.e. (b+a)* c then c will compulsory will be in the prefix. But in the longest prefix there is "c" coming at last . Even if we take any option of T3 then "c" will get generated at starting of the prefix of string compulsorily { MY NEW VOCABULARY :)}

Can somebody explain ? 

---

•  T1 : (b+c)* a + a(b+c)* a

•  T2 : (a+c)* b + b(a+c)* b

•  T3 : (b+a)* c + c(b+a)* c

So this is the three expression given 

we have given the string     “bbaacabc”

First, we take T1 and generate: bb

Then T2 and generated:  aac

Then T3 and generated: abc

How this approach is wrong?

 

---

@princeit07 using T1 you can never generate bb because ‘a’ will always come after ‘bb’. 

The question has asked about longest common subsequcnce that’s why we are considering T3T3 as the correct answer.

Answer 2

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.

Comments

needs correction in option A

Answer 3

option D is correct

bbaac -> this can be generated by T₃ 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 T₃T₃

Answer 4

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.