in Theory of Computation edited by
1,377 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 ?
in Theory of Computation edited by
1.4k views

15 Comments

edited by
$n(a)' \text{s should be multiple of n(b)'s}.$
$L = \{a^nb^n | n \geq1\}  \cup \{a^{2n}b^n | n \geq1\} \cup \{a^{3n}b^n | n \geq1\}...............$
It's $infinite \ union$ of $CFL$ and we have only finite number of states in $PDA$. So $L$ is $CSL$.​​​​​
4
4

@Soumya29 can you write cfg for this?

0
0

@Soumya29 you need to have too many (infinite) states right one each for every value of m (when the reading b)??

0
0
$L$ is not CFL should be true
0
0

@Utkarsh  @Hemanth @Shobhit 
Yes, infinite union is there. $L$ is not $CFL$. 

0
0
Yes I think it is CSL
0
0
yes $CSL$
0
0

@Soumya29

@Utkarsh Joshi

@Hemanth_13

Is this always true .infinite union of CFL is not CFL ..or it is like CFL are not closed under infinite union..where it may or may not be CFL...

just like regular langauage where infinite union of regular languages may / may not be regular

------------------------------------------------------------------------------------------------------------------------------

And in above example if  1<= m<= constant

Then it will finite union ..and hence finite union of CFL is CFL ..BUT IT IS NCFL here right ??

0
0
Yes you will then have finite states (to handle b)which will make it NCFL.
0
0

 ....or it is like CFL are not closed under infinite union..where it may or may not be CFL...

Yes. May or may not CFL. 

And in above example if  1<= m<= constant
Then it will finite union ..and hence finite union of CFL is CFL ..BUT IT IS NCFL here right ??

Yes.. 

0
0
0
0
Not CFL
0
0

It's infinite union of CFL and we have only finite number of states in PDA. So L is CSL.​​​​​

 @Soumya29 , You might wanna edit this statement because It isn't correct in General. You might wanna say "Infinite Non-determinism" instead of "infinite union".. 

0
0
Yes ..even sometime infinite union of languages can be accepted using finite state machine ..

L1{a},L2(aa),L3{aaa} .....

L  = L1$\cup$ L2 $\cup$ L3......==> a^+

Can be done in one state PDA..
0
0

@Deepakk sir,
 You might wanna say "Infinite Non-determinism" instead of "infinite union".. 

Yes, I wanna say this only. I used the wrong terminology. Thanks for the correction :) 

0
0

1 Answer

8 votes
8 votes
Best answer
$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

3 Comments

well explained!
0
0
thanks, sir.
0
0
Gzb explanation Deepak bhaiyaa:)
0
0