edited by
1,362 views
2 votes
2 votes
L = { $a^{nm}b^{n} | n,m\geq 1$ }

L is DCFL  OR

L is CFL but not DCFL OR

L is not CFL

which one is true ?
edited by

1 Answer

Best answer
8 votes
8 votes
$L = \{ a^{mn} b^n | n,m \geq 1 \}$

$L$ is a Non-CFL CSL.

We can use "Pumping lemma for CFL" to prove that $L$ is Not a CFL.

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$ 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+1)(P+1)} b^{(P+1)}$, Now Try to split it into five parts $uvxyz$ such that All the Three conditions of pumping lemma must satisfy.

To make further things easy for us, I can assume, without loss of generality, that our constant  $P$ is such that $P+1$ is a Prime. NOTE that I, indeed, can, without loss of generality, assume this because Pumping lemma says that There exists some $P$ such that for all strings $w$ such that $|w| \geq P,$ we have a Partition satisfying all the three conditions.  So, I can push $P$ to the limit such that $P+1$ is a Prime.

Now, You can Try splitting the string $a^{(P+1)(P+1)} b^{(P+1)}$, according to the pumping lemma. But You won't find any Partition satisfying all the three conditions simultaneously. I'll give Hints for the splits possible.

Hints :

Case 1 : $v\,\,and\,\,y$ each  contain only one type of symbol. i.e. $v,y$ both are entirely in either $a's$ part or Both are entirely in $b's$ part : You will find that no matter How you pick $v,y,$ the third condition will surely violate.

Case 2 : $v$ is in $a's$ part and $y$ is in $b's $ part :  You will find that no matter How you pick $v,y,$ the third condition will surely violate.

So, We have shown at least one string $w$ such that $|w| \geq P, $ for which pumping lemma conditions Do Not Hold. Hence, Our Assumption that $L$ was a CFL, was Wrong.

Hence, by Contradiction, $L$ is Not a CFL.

P.S. :

1. In GATE exam, You must Not apply Pumping lemma as It is Time taking and Error Prone(Needs quite a practice). Moreover, if $L$ satisfies the pumping lemma, You can't say anything about it because some Non-CFL also satisfy Pumping lemma for CFL.

2. Without Pumping lemma, One can check intuitively that $L$ is Not CFL. Adding to the idea that  @Soumya29  has given in the comments to the question.

$n(a)′s$ should be multiple of $n(b)'s.$
$L= \{a^nb^n|n≥1 \}∪ \{a^{2n}b^n|n≥1 \}∪ \{a^{3n}b^n|n≥1 \}....... $

 Now, here we need infinite Non-determinism to accept this language.

I mean, Let $L$ be $ \{a^nb^n|n≥1 \}∪ \{a^{2n}b^n|n≥1 \} $, then "informally"(in non-technical simple words), we need Non-determinism of size two (Guess either $ \{a^nb^n|n≥1 \} $  or $ \{a^{2n}b^n|n≥1 \} $ )

Or if $L$ be $L= \{a^nb^n|n≥1 \}∪ \{a^{2n}b^n|n≥1 \}∪ \{a^{3n}b^n|n≥1 \} $ then "informally"(in non-technical simple words), we need Non-determinism of size three (Guess either $ \{a^nb^n|n≥1 \} $ or $ \{a^{2n}b^n|n≥1 \} $ or  $\{a^{3n}b^n|n≥1 \}$ )

So, extending this idea, we need Infinite Non-determinism for the $L$ given in the question.

Which is Not possible by PDA.
edited by

Related questions