The Gateway to Computer Science Excellence
+1 vote

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

above language is DCFL,NDCFL or CSL?

in Theory of Computation by Boss (12.3k points) | 256 views

1 Answer

+5 votes
Best answer

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 by
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,356 answers
105,254 users