The Gateway to Computer Science Excellence

+21 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)^*a$

$T_2$: $b?(a \mid c)^*b$

$T_3$: $c?(b \mid a)^*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 processes by the analyzer, which one of the following is the sequence of tokens it outputs?

- $T_1T_2T_3$
- $T_1T_1T_3$
- $T_2T_1T_3$
- $T_3T_3$

+3

I also got T_{3}T_{3}, as the question specifically mentioned that it will prefer the relational algebra which generates the **longest subsequence**.

0

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

+34 votes

Best answer

**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.

+2

it regular expression is like this (ε+a)(b+c)∗a we have zero or one a followed any b or c and end with a

+1

can we discuss why remaining options are wrongs, I understand the concepts for above question, My doubt in options 3, T_{2} T_{1}T_{3. }Is this reg expression also capable to generate bbaacab???

can I wrote like this, T_{2 }can generate bb, T_{1} can generate aa and from T3 cabc

this option is wrong just because in question asking for longest possible prefixes or something else reason???

0

bbaacabc

Can someone please check what are lexemes here

b(T1), bb(T2) , bba(T1) , bbaa(X) , bbaac(T3)

abc(T3)

Can someone please check what are lexemes here

b(T1), bb(T2) , bba(T1) , bbaa(X) , bbaac(T3)

abc(T3)

0

this option is wrong just because in question asking for longest possible prefixes

yes.

b(T1), bb(T2) , bba(T1) , bbaa(X) , bbaac(T3)

we get **b** by T_{2} but not by T_{1} .

0

because question is asking token that matches the longest possible prefix, thats why answer is T3T3 as first T3 is generating "bbaac" substring of length 5 which is longest prefix among all the possibilities from the option, thats why answer is (D)

0

I feel that from option c we can't generate string bbaacabc because in the ques it is said that "x?" means 0 or 1 occurrence of symbol x. So if we start with T2 then we can generate only a single b, from T1 we can generate only ba, from T3 we can generate only ac.. So from T2T1T3 we can generate only bbaac which is not the required string. So option c is wrong. Please check @Hira Thakur

+9 votes

**option D is correct**

bbaac -> this can be generated by T_{3} 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 _{3}T_{3}**

+6 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.

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.

+5 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.

+2 votes

The answer is T_{3}T_{3 }as the question specifically mentioned that it will prefer the relational algebra which generates the **longest subsequence**.

With T_{3} you get a subsequence of **5**, whereas with T_{2} you get a subsequence of only **3**.

Hence, T_{3} preferred over T_{2}.

So option **D** is the correct answer.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,335 answers

198,445 comments

105,201 users