edited by
4,013 views
13 votes
13 votes

L1 = { a^i b^j c^m | m ≥ min(i,j) }

L2 = { a^i b^j c^m | m ≥ max(i,j) }

Which language is CFL ?

ANS : L1 is CFL but L2 is NOT.

My understanding : 

For Language L1 :

( Here I am interested in checking Whether language is DCFL or not , also. ) 

Checking DCFL or not : 

By looking at language , it is not possible to construct PDA as it contains 2 conditions (  i > j or i < j  And m ≥ min (i,j) ) 

But there is a way of checking language is DCFL or not. ( By Prefix Property ) 

No Proper Prefix ⇢ Prefix property ⇢ DCFL 

But there is No Proper Prefix getting for this language ,  So, Prefix property , and so L1 is  DCFL  ( but there is no DPDA for L1 as per my 1st conclusion ( i.e. 2 conditions -> No PDA ) 

It means somewhere I am wrong. Please correct me. 

Checking CFL or not : 

We will have to check whether it is accepted by NPDA or not.

I dont know correct way to construct NPDA but I tried in following way.
1) At some point PDA will assume that i < j or i > j
condition 1st : i < j
We are interested in min , so consider only i,≥ means accept "a" and skip all "b" and for each "c" , pop each "a"
Condition 2nd: i > j
We are interested in min , so consider only j means skip all "a" and accept "b" and for each "c" , pop each "b" So it is CFL. Please correct me if it is wrong.
If above NPDA is right , then we can construct NPDA for L2 also.
But Answer part saying L2 is not CFL.

So above NPDA is right or wrong ??

edited by

2 Answers

Best answer
22 votes
22 votes

Prefix property is not obeyed by all DCFLs. It is obeyed only by those languages accepted by a deterministic PDA which accepts by empty stack- if a prefix of the string is in L, stack should have been empty before and deterministic means, this cannot happen.

Now, a language obeys prefix property doesn't mean it is DCFL. {anbnc| n ≥ 1} obeys prefix property but not even CFL. 

L1 = { ai bj cm | m ≥ min(i,j) }

Here number of c's is greater than minimum of number of a's and number of b's. So, we can say that if number of c's is greater than number of a's or if number of c's is greater than number of b's, we accept. i.e.,

L1 = { aibjcm | m ≥ i OR m ≥ j) }

The OR condition here means even though we need to do two checks, we can accept in either case and hence using non-determinism we just need a PDA to accept L1 (we non-deterministically check if m ≥ j and if m ≥ i). So, L1 is a CFL but not DCFL. 

L2 = { ai bj cm | m ≥ max(i,j) }

This can be rewritten as 

L2 = { aibjcm | m ≥ i AND m ≥ j) }

The AND condition here means we need to do two checks and even  non-determinism cannot help us here. This is because if we non-deterministically guess i ≥ j, and accept if m ≥ i, suppose if the guess is wrong, then we would have accepted a word not in L2. (In short non-determinism can help only when we have OR condition). So, L2 is not even CFL- it is a CSL. 

selected by
1 votes
1 votes
Before answering I'll give you two points to see:

Σ* is a language which doesn't satisfy prefix property- (if w is in L, prefix of w can also be in L). Now, is this language not DCFL?

Your PDA for L1 is right. But suppose you use the same PDA (suitably changed) for L2. It will accept aaabcc rt? And aaabcc is not in L2.

Related questions

0 votes
0 votes
2 answers
2
Ravi Raaja asked Sep 17, 2015
2,212 views
how to construct pda for a^i b^j where j!=2i+1, i>=0 ?i have constructed for j=2i+1 but by complementing the states do we get actual n pda of our requirement?whether it i...