+1 vote
256 views

L1={an bm│m≠n and m≠2n}

above language is DCFL,NDCFL or CSL?

| 256 views

This language can be decomposed into 3 parts :

Let the first part be : a) La  =  { an b| m < n }  which we know is decidable

b) Lb  =  { an bm | n < m < 2n } ..Now this can be further decomposed as : { an bn+1 } U { an bn+2 } ........ U { an b2n-1 }

Now each of the components mentioned above are DCFLs..However if we take union , we can clearly see non determinism as soon as 'a' is finished scanning and 'b' comes in the input..Hence this part is not DCFL but yes it is NDCFL as only one of the above needs to be followed at a time..

c) Lc  = { an bm | m > 2n } which is again a DCFL..

So the given language L1 in the question is nothing but the union of the above 3 cases as the both the language conditions given in the question m != n and m != 2n are met by the above explained 3 cases and also all strings will be covered..

Hence for deciding language class , we do nothing but union of a) , b) and c) cases which are DCFL , NDCFL and DCFL respectively..

Hence the union is going to be a NDCFL language..

Hence L1 is NDCFL

by Veteran (102k points)
selected