The Gateway to Computer Science Excellence
0 votes
76 views
$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 Active (3.5k points)
edited by | 76 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. 

https://gateoverflow.in/302817/gate2019-31?show=303668#a303668

by Boss (26.4k points)
0
Thanks Brother.. :)
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
50,644 questions
56,531 answers
195,625 comments
101,353 users