The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+15 votes
4.1k views

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?

  1. $T_1T_2T_3$
  2. $T_1T_1T_3$
  3. $T_2T_1T_3$
  4. $T_3T_3$
asked in Compiler Design by Boss (18.2k points)
edited by | 4.1k views
+1
d  how????
+1
d option
+1
t3t3 is answer
0
I think b option is also correct try to pardeparse the string using t1t1t3 it works fine. .  Seems to be ambigous question. .
+6
longest possible prefix matched with the string is "bbaac" generated by T3 and then "abc" by T3, so T3T3 is the answer.
0
what is meant  by ? in regex
0

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

5 Answers

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

answered by Active (2.9k points)
edited by
0
Option d is correct..see Note in question.
0
what is the meaning of the line

 

T1: a?(b∣c)∗a
0
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
0

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

can I wrote like this, T2 can generate bb, T1 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)
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 T2 but not by T1 .

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)
+7 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

answered by Boss (10.3k points)
+1 vote
Marked D as well
answered by (263 points)
+1
correct.
+2

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

+1 vote

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

With  T3 you get a subsequence of 5, whereas with T2 you get a subsequence of only 3.

Hence, T3 preferred over T2.

So option D is the correct answer.

answered by (343 points)
0
How did you get subsequence of 3 from T2? i am getting only "bb' which is subsequence of 2.
0 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.

answered by (115 points)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,434 questions
53,630 answers
186,007 comments
70,899 users