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

$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

+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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,644 questions

56,531 answers

195,625 comments

101,353 users