edited by
3,499 views
2 votes
2 votes

Given the following two languages:

  • $L_1=\{a^nba^n\;|\;n>0\}$
  • $L_2=\{a^nba^nb^{n+1}\;|\;n>0\}$

Which of the following is correct?

  1.  $L_1$ is context free language and $L_2$ is not context free language
  2.  $L_1$ is not context free language and $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
edited by

3 Answers

Best answer
7 votes
7 votes
Answer : A

A. L1 is context free language (deterministic) and L2 is not context free language

For L1, we need to count the number of a's before and after 'b' and this length is not finite. Hence, it is DCFL and not regular.

For L2, in addition to above comparison, we also need to ensure number of b's following the a's is just one more. This is a second non-finite comparison and cannot be done with just one stack. So, this makes L2 a CSL.
edited by
3 votes
3 votes
$L_1=\{a^nba^n\;|\; n>0\}$ is CFL

push $a's$ in stack ,do nothing with $b$ , then pop $a's$ from stack on reading $a's$

$L_2=\{a^nba^nb^{n+1}\;|\; n>0\}$ is CSL.

Push $a's$ in stack, donothing on $b$ , pop $a's$ from stack on reading $a's$, then we left with $b's$ with empty stack, then we can't ensure these $b's$ are one more that earlier $a's$.

Option $A$, $L_1$ is context free and $L_2$ is not context free language.
0 votes
0 votes

l1 :is language for which we cant write regular expression and it need stack  for comparison  so it is CFL
l2 eg: a^3ba^3b^4
first push all three a's in stack than when b comes pop all upconing a's with those a's which are present in stack ..now at this point one comparison is over..now 4 b''ss comes neglect them or we can say do thing with them so we left with empty stack so it is also CFL..
so (c) option 

Answer:

Related questions

4 votes
4 votes
1 answer
1
go_editor asked Aug 9, 2016
3,074 views
Match the following $:$$\begin{array}{clcl} & \textbf{List – I} & & \textbf{List – II} \\ \text{(a)} & \{a^n b^n \mid n 0\} \text{ is a deterministic } & \text{...
2 votes
2 votes
2 answers
2
go_editor asked Aug 9, 2016
2,093 views
The family of context sensitive languages is _____ under union and ____ under reversalclosed, not closednot closed, not closedclosed, closednot closed, closed