The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
Which of the following language is DCFL?

L1 = { a^n b^m : n $\neq$ m : n,m > 0 }

L2 = { a^n b^m c^k  : m>n or m < n }
asked ago in Theory of Computation by (55 points) | 57 views

L1 is not the complement of {anbm where n=m}. Because complement means (a+b)*-L1 = (a+b)*-anbwhich can generate many strings like {abab,babba ..} basically anything which are not of anbn this form. However we can still create DPDA for language L1.

Please refer to the 2nd answer here

[Don't see the other answers there]

So L1 is a DCFL.

Second one, that also can be reduced to the first problem. It says that the number of a's and b's are not equal (either n(a)>n(b) or n(a)<n(b) ). So ultimately same as above. And we don't need to take any action(pushing or popping) for c's as it doesn't need to be compared with anything. So this is also a DCFL.


i think we can take it as L1=(a+b)* - (anbn)

                                           =reg. lang. - DCFL

                                           = RL INTERSECTION DCFL'

                                           =DCFL  always.

and second one is same as 1.


arvin Your derivation seems correct but tell me one thing..


After this we can say that RL can be promoted to DCFL. Then it becomes

DCFL intersection DCFL

which may not be a DCFL as they are not closed under intersection.

Am i going wrong somewhere?


arvin If i had understood correctly, they have stated that

If C is regular and D is context free, then CD is context free (I'm not sure what happens if D is a DCFL, whether the intersection also is, but it's at least still context free).

Though CFLs are also not closed under intersection.

Another one :

MN=MN' (where N is regular and M is DCFL) you would also need closure under intersection. Unfortunately, DCFLs are not closed under union nor intersection.


@minipanda : i think dcfl's are not closed under union or intersection when we are operating between two dcfls.
and here we are intersecting dcfl with regular language.
for example : a*b* intersection anbn is anbn which is dcfl
                      b*a* intersection anbn is phi which is also a dcfl. n>1;

i think dcfl's are not closed under union or intersection when we are operating between two dcfls.

But regular languages are also DCFL. In that way their intersection shouldn't always be DCFL. By "we are operating between two dcfls" do you mean languages which are strictly DCFL and not regular? If that is the case then my doubt is cleared. This is a thing to be noted. I have followed the same derivation process earlier as you have done but then suddenly this thought came up :P

Moreover I can't really think of any example to show REG intersection DCFL is not DCFL.  But going by the previous logic i couldn't be ascertain about it.

@minipanda to be honest i dont know if we can promote reg lang to dcfl or not for proving any property but what i have read many places is that intersection of any language(reg,dcfl,cfl,csl,re,rel) with regular language is the same language.
+1 refer to this ! i think this is the last proof i have! :p see option a only!


Yes thank you arvin  :D

Please log in or register to answer this question.

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

38,053 questions
45,545 answers
48,885 users