The Gateway to Computer Science Excellence
0 votes
$L1 =\left \{ a^{m} b^{n} c^{p} | \left ( m \geq n \right )\text{or} \left ( n = p \right ) \right \}$  
$L2 =\left \{ a^{m} b^{n} c^{p} | \left ( m \geq n \right )\text{and} \left ( n = p \right ) \right \}$

$(a)$ Both are NCFL’s

$(b)$ L1 is DCFL and L2 is NCFL

$(c)$ L1 is NCFL and L2 is not context-free

$(d)$ Both are not context-free
in Theory of Computation by
edited by | 163 views

1 Answer

+2 votes

Answer : C

$L_1 = \{ a^mb^nc^p| m \geq n \,\, Or\,\,n = p \}$

We can write $L_1$ as a Union of two languages : $L_1 = \{ a^mb^nc^p|m\geq n \} \,\, \cup  \{ a^mb^nc^n\}$

$L_1$ is CFL and we can easily write CFG for this language as following :

$S \rightarrow AB$ (This will create $a^*b^nc^n$ which is same as $a^mb^nc^n$  ) $\,\,|\,\,ADF$ (This will create $a^*a^nb^nc^*$ which is same as $a^mb^nc^p|m\geq n$)

$A \rightarrow aA|\in$         // $A $ will create $a^*$

$B \rightarrow bBc|\in$       // $B $ will create $b^nc^n$

$D \rightarrow a D b|\in$      // $D$ will create $a^nb^n$

$F \rightarrow cF|\in$         //$F$ will create $c^*$

Alternate Solution :

Informal idea for PDA construction is that one branch in PDA will check for $m \geq n$ and other branch will check for $n = p$ and if either one of these branches go to final state at the end of the string then the string is accepted. 

$L_1$ is Not DCFL because DPDA cannot decide PUSH and POP certainely because there is No Non-determinism facility available like in PDA.

$L_2 = \{ a^mb^nc^t| m \geq n \,\, And\,\,n = t \}$

$L_2 $ isn't CFL and we can prove it using Pumping lemma for CFLs. 

Pumping lemma for CFLs:

Let $L$ be a CFL. Then there exists some integer constant $P \geq 1$ (Called Pumping length or pumping-lemma constant)  such that if $w ∈ L$ with $|w| ≥ P,$ then we can write $w = uvxyz,$ subject to the following conditions:

1. $|vxy| ≤ P.$

2. $vy \neq \in .$

3. For all $i ≥ 0,$ we have $uv^ixy^iz ∈ L.$

i.e. Informally, For every sufficiently large string $w$ in $L,$ We must be able to split it such that it is possible to find at most two short, nearby substrings that we can “pump” $i$ times in tandem, for any non-negative integer $i,$ and the resulting string will still be in that language.  

Now, Assume that Given $L_2$ is CFL, Hence, It will satisfy Pumping lemma for CFL.

So, There must be some integer constant (pumping length) $\geq1$ exists for this language. Let it be $P.$

So, Now for every string $w \in L$ whose length is greater than or equal to $P,$ we must have some partition $uvxyz$ satisfying all the above conditions.

So, Let me take the string $a^{P} b^{P}c^{P} \in L_2$, Now Try to split it into five parts $uvxyz$ such that All the Three conditions of pumping lemma must satisfy.

Basically in Pumping lemma for CFL, You want to find $"$at most $P"$ consecutive symbols in the String(anywhere in the String) such that you can find two short sub-strings in that part and Pump those sub-strings in tandem. 

But for the above String  $a^{P} b^{P}c^{P}$, we cannot find any such at most $P$ consecutive symbols anywhere in the string which will satisfy the Pumping lemma conditions. (Hint : Check different possibilities i.e. Take Those at most $P$ consecutive symbols in completely in $a^P$ part or completely in $b^P$ part or completely in $c^P$ part or some in $a^P$ part and some in $b^P$ part or some in $b^P$ part and some in $c^P$ part   of the string .. etc.. covering all possible partitions..  )

So, Given language doesn't satisfy Pumping lemma and hence, $L$ is Not CFL.

The Informal idea behind Non-CFLness of $L_2$ is that PDA needs to do two comparisons simultaneouly in same string and both comparisons must turn out to be True. But if PDA compares $m,n$ then we have run out of $b's$ so now we can't compare $n,p.$ Similarly, if PDA compares $n,p$ then also we have run out of $b's$ so we cannot compare $m,n.$

For more examples to understand Pumping lemma for CFLs, Refer my answer on this GATE question.

Thanks Brother.. :)

@Deepakk Poonia (Dee) 
I think that L1 is a  deterministic context free language.
Please verify?

No, L1 isn't DCFL.

I have mentioned it in the answer.

What's your argument behind it being DCFL?



I have drawn the PDA for this.
IN this PDA we donot have different transitions for the same input symbol and same stack top symbol.Hence this is a DPDA.right?

I went through the DPDA portion of Peter Linz.and it has been told that if we have an epsilon transition  from a state A then no input consuming alternative should be available in state A.
I think the  epsilon-transition from A to B in the diagram (even after having input consuming moves in A) makes it an NPDA.right?



Yes, that's where you have non-determinism. You should see that if you are making epsilon move from some state Q with TOS symbol T then you should not have any transition on any input symbol from that state(Q) with that TOS symbol(T).
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,506 answers
95,341 users