recategorized by
974 views
0 votes
0 votes

Consider the following languages:

$L_1 = \{ a^{n+m} b^n a^m \mid n, m \geq 0 \}$

$L_2 = \{ a^{n+m} b^{n+m} a^{n+m} \mid n, m \geq 0\}$

Which of the following is correct ?

$Code:$

  1. Only $L_1$ is context free language
  2. Only $L_2$ is context free language
  3. Both $L_1$ and $L_2$ are context free languages
  4. Both $L_1$ and $L_2$ are not context free languages
recategorized by

1 Answer

1 votes
1 votes
$L_1 = \{\;a^{n+m}.b^n . a^m \;|\; n,m ≥ 0 \;\} = \{\;a^{m}.a^n.b^n . a^m \;|\; n,m ≥ 0 \;\} $

Push all a's, Pop every a for one b,

Now there are only m number of a's in stack,

Now, Pop every a for one a, ==> if it is empty stack, then accept

∴ CFL

 

$L_2 = \{\;a^{n+m}.b^{n+m} . a^{n+m} \;|\; n,m ≥ 0 \;\} = \{\;a^{x}. b^x . a^x \;|\; x ≥ 0 \;\} $ where x = n+m

it is CSL but not CFL
Answer:

Related questions

1 votes
1 votes
3 answers
1