1,561 views

3 Answers

2 votes
2 votes
ANSWER SHOULD BE 3)

only a^nb^n

REASON:

  if we look at question it seems that 1st and 2nd languages are DETERMINISTIC CFL nad language 3 is NON-DETERMINISTIC language.....but

IN QUESTION STACK ALPHABET='z0' and 'a'...so ultimate meaning is that in any and how condiction only z0 and a can be in stack ......

for language 1...that is a^nb^n we can find language just for pushing every 'a' and for every 'b' ...pop 'a' without doing any other action....

but for languages 2 and 3 we cant find them without pushing 'a' and 'b' ...so they cant be found....

conclusion is that .....all languages can be found but ....due to restriction on STACK ALPHABET....only a^nb^n is possible....
0 votes
0 votes
ans should be a.

all three are context free languages
0 votes
0 votes
answer should be iii) i.e I only,  in PDA it is not necessary what symbols we push as they are just representatives for counting the no. of symbols in the question

but for

II) PDA will push the a’s for a and b till it encounters # and then it will pop single a for each symbol so it cannot ensure reverse is present it can only ensure that no. of symbols before and after # are equal

same goes for III

Related questions

0 votes
0 votes
1 answer
3