Register

ISRO-DEC2017-26

• recategorized by
1,213 views
5 votes
5 votes

Which of the following are context-free?

$A=\{a^n b^n\, a^mb^m\mid m,n\geq0\}$
$B=\{a^m b^n\, a^mb^n\mid m,n\geq0\}$
$C=\{a^mb^n\mid m\neq 2n,\,m,n\geq0\}$

  1. A and B only 
  2. A and C only
  3. B and C only
  4. C only
• recategorized by
User Avatar

2 Answers

Best answer
6 votes
6 votes
  • A is context free : push a′s into stack, for each b's pop the stack. If stack is empty, then string is  accepted
  • B is NOT context free. Single stack is not sufficient because m and n are not comparable we cannot find when to push or pop;
    • But this is CSL.
  • C is context free : push a′s into stack, for each b's pop the stack two times. If stack is empty, then string is  NOT accepted

Answer is B ) A and C Only

• selected by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
gatecse asked Dec 17, 2017
1,037 views
ISRO-DEC2017-25
Let $L=\{a^p\mid p \text{ is a prime}\}.$ Then which of the following is true It is not accepted by a Turing Machine It is regular but not context-free It is context-free but not regular It is neither regular nor context-free ,but accepted by a Turing Machine
Let $L=\{a^p\mid p \text{ is a prime}\}.$ Then which of the following is trueIt is not accepted by a Turing MachineIt is regular but not context-freeIt is context-free b...
User Avatar
4 votes
4 votes
1 answer
2
gatecse asked Dec 17, 2017
1,325 views
ISRO-DEC2017-24
Let $L_1$ be regular language, $L_2$ be a deterministic context free language and $L_3$ a recursively enumerable language, but not recursive. Which one of the follewing statements is false ? $L_3\cap L_1$ is recursive $L_1\cap L_2\cap L_3$ is recursively enumerable $L_1\cup L_2$ is context free $L_1\cap L_2$ is context free
Let $L_1$ be regular language, $L_2$ be a deterministic context free language and $L_3$a recursively enumerable language, but not recursive. Which one of the follewing st...
User Avatar
3 votes
3 votes
2 answers
3
gatecse asked Dec 17, 2017
2,019 views
ISRO-DEC2017-23
Identify the language generated by the following grammar $S\rightarrow AB\\ A\rightarrow aAb\mid \varepsilon\\ B\rightarrow bB\mid b$ $\{a^m b^n\mid n\geq m,m>0\}$ $\{a^m b^n\mid n\geq m,m\geq0\}$ $\{a^m b^n\mid n> m,m>0\}$ $\{a^m b^m\mid n> m,m\geq0\}$
Identify the language generated by the following grammar$S\rightarrow AB\\ A\rightarrow aAb\mid \varepsilon\\ B\rightarrow bB\mid b$$\{a^m b^n\mid n\geq m,m>0\}$ $\{a^m b...
User Avatar
4 votes
4 votes
2 answers
4
gatecse asked Dec 17, 2017
3,420 views
ISRO-DEC2017-22
Consider the grammar with productions $S\rightarrow aSb\mid SS \mid \varepsilon$ This grammar is not context-free, not linear not context-free, linear context-free, not linear context-free, linear
Consider the grammar with productions$S\rightarrow aSb\mid SS \mid \varepsilon$This grammar is not context-free, not linearnot context-free, linearcontext-free, not linea...
User Avatar
Link Copied!