1
$\begingroup$

$L_1 = \{ a^i b^j c^m \mid m ≥ min(i,j) \}$

$L_2 = \{ a^i b^j c^m \mid m ≥ max(i,j) \}$

Which language is CFL ?

ANS : $L_1$ is CFL but $L_2$ is NOT.

My understanding : 

For Language $L_1$ :

( Here I am also interested in checking whether the language is DCFL or not. ) 

Checking DCFL or not : 

By looking at language $L_1$, 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 $L_1$ is  DCFL  ( but there is no DPDA for $L_1$ 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 don't know correct way to construct NPDA but I tried in following way.

At some point the 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 the above NPDA is right, then we can also construct an NPDA for $L_2$.

But the Answer part says $L_2$ is not CFL.

So is the above NPDA is right or wrong ??

enter image description here

$\endgroup$
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Jun 14 '17 at 16:22
  • $\begingroup$ Even after explaining what I did, I am just asking can someone explain the answer? $\endgroup$ – Aditya Jun 14 '17 at 23:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.