edited by
20,917 views
50 votes
50 votes

Consider the following languages:

$L_{1}=\left\{a^{n}b^{m}c^{n+m}:m, n\geq 1\right\}$

$L_{2}=\left\{a^{n}b^{n}c^{2n} :n\geq 1\right\}$

Which one of the following is TRUE?

  1. Both $L_{1}$ and $L_{2}$ are context-free.
  2. $L_{1}$ is context-free while $L_{2}$ is not context-free.
  3. $L_{2}$ is context-free while $L_{1}$ is not context-free.
  4. Neither $L_{1}$ nor $L_{2}$ is context-free.
edited by

5 Answers

Best answer
64 votes
64 votes

$L_1=\{a^nb^mc^{n+m}\; :\; m,n\geq1\}$  is Context-free language

(push $a's$ into stack, then push $b's$ into stack , read $c's$ and pop $b's$ , when no $b's$ left on stack, keep reading $c's$ and pop $a's$ , when no c's left in input , and stack is empty, then accepted).

$L_2=\{a^nb^nc^{2n}\; :\; n\geq1\}$ is Context-sensitive language and not context-free. (cannot implemented by one stack)

So, answer is option B.

edited by
49 votes
49 votes
I think only L1 is context free .

Since L1 is explained by others I will take L2

In L2 we can push all a's and all b's onto the stack and on seeing each c we can pop out 1 b and after all b's are popped off we can pop all a's .

that way a^nb^n will be same in number as c^2n and ultimately we can attain empty string or bottom of the stack .

But the problem with this approach is that it will accept strings which are not in the language like abbbcccc.

OPTION  : B
edited by
5 votes
5 votes

 L1 is explained by others it’s context-free,  I will take L2.

If you are thinking that you will push all the ‘a’ s then all the ‘b’ s and seeing each ‘c‘ pop ‘b’ then pop ‘a’ s and if at the end stack is empty then the string will be accepted. You are WRONG. Here you are not checking the number of ‘a’ and the number of ‘b’ are equal or not. So your PDA will also accept strings present in L1. Ex: “abbccc” , “aabccc” etc.

If you are thinking that you will check first the number of ‘a’ and the number of ‘b’ are equal or not. Then first you will push all the ‘a’ and when you will see all ‘b’ you will start popping ‘b’, when there is no ‘b’ left if the stack is empty then the number of a and b are the same. Your approach is WRONG. Here the problem is your stack is empty now how will you check that number of ‘c’ is double of a and b or not.

1 votes
1 votes

L1 can be recognized by PDA, we have to push a’s and b’s in stack and when c’s comes then pop every symbol from stack for each c’s.
At the end if input and stack is empty then accept.
Hence, it is CFL.

But L2 can’t be recognized by PDA, i.e. by using single stack.
The reason is, it has two comparison at a time,
1st comparison:
number of a’s = number of b’s
2nd comparison:
number of c’s must be two times number of a’s (or b’s)
It is CSL.

Answer:

Related questions

38 votes
38 votes
5 answers
3
Akash Kanase asked Feb 12, 2016
15,597 views
The number of states in the minimum sized DFA that accepts the language defined by the regular expression.$(0+1)^{*} (0+1) (0+1)^{*}$is ________.