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 ??