edited by
14,931 views
44 votes
44 votes

Which of the following languages are context-free?

$L_1: \left\{a^mb^na^nb^m \mid m, n \geq 1\right\}$

$L_2: \left\{a^mb^na^mb^n \mid m, n \geq 1\right\}$

$L_3: \left\{a^mb^n \mid m = 2n +1 \right\}$

  1. $L_1$ and $L_2$ only
  2. $L_1$ and $L_3$ only
  3. $L_2$ and $L_3$ only
  4. $L_3$ only
edited by

2 Answers

Best answer
59 votes
59 votes

first check for $L_1$. now look $a^m$ & $b^m$ and $a^n$ & $b^n$ must $be$ comparable using one stack for CFL.
now take a stack push all $a^m$ in to the stack  then push all $b^n$ in to stack now $a^n$ is coming so pop $b^n$ for each $a^n$ by this $b^n$ and $a^n$ will b comparable. now we have left only $a^m$ in stack and $b^m$ is coming so pop $a^m$ for each $b^m$ by which we can compare $a^m$ to $b^m$ ..we conclude that we are comparing this $L_1$ using a single stack so this is CFG.

now for $L_2$.this can not be done in to a single stack because $m$ and $n$ are not comparable we can not find when to push or  pop so this is CSL.

now for $L_3$.push all $a$'s into stack and pop $2a$ 's for every $b$  and at last we left with a single $a$ .
bcz here $aaaaabb$ is a valid string where $m=2n+1$ and $n=2$. So realized using single stack hence $L_3$ is CFG.

so the option is B.. $L_1$ and $L_3$ are CFG

edited by
2 votes
2 votes

L1: First push all the a's in the stack then push all the b's in the stack. Now pop all the b's from the stack watching next no. of a's. And then pop all the a's from the stack watching next no. of b's. So can be done by PDA, hence CFL.

L2: First push all the a's in the stack then push all the b's in the stack. Now again a's come which cannot be compared by previous a's in the stack because at top of the stack's there are b's which is also needed to be pushed for further comparision with the next b's. So not CFL.

L3: First simply read one 'a', then push one 'a' in the stack after reading two a's and then pop all the a's by reading the b's. Since can be done by PDA hence CFL.
Option B

Answer:

Related questions

55 votes
55 votes
5 answers
2