0 votes 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 } Vipin Rai asked Aug 11, 2018 Vipin Rai 2.0k views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply MiNiPanda commented Aug 11, 2018 reply Follow Share L1 is not the complement of {anbm where n=m}. Because complement means (a+b)*-L1 = (a+b)*-anbn which 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 https://www.quora.com/What-would-be-the-PDA-for-a-n-b-m-where-n-neq-m [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. 1 votes 1 votes arvin commented Aug 11, 2018 reply Follow Share 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. 0 votes 0 votes MiNiPanda commented Aug 11, 2018 reply Follow Share arvin Your derivation seems correct but tell me one thing.. RL INTERSECTION DCFL' 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? 0 votes 0 votes arvin commented Aug 11, 2018 reply Follow Share @minipanda : https://math.stackexchange.com/questions/388297/are-regular-languages-necessarily-deterministic-context-free-languages refer to this once. 0 votes 0 votes MiNiPanda commented Aug 11, 2018 reply Follow Share arvin If i had understood correctly, they have stated that If C is regular and D is context free, then C∩D 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 : M−N=M∩N' (where N is regular and M is DCFL) you would also need closure under intersection. Unfortunately, DCFLs are not closed under union nor intersection. 0 votes 0 votes arvin commented Aug 11, 2018 reply Follow Share @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; 0 votes 0 votes MiNiPanda commented Aug 11, 2018 reply Follow Share 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. 0 votes 0 votes arvin commented Aug 11, 2018 reply Follow Share @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 votes 1 votes arvin commented Aug 11, 2018 reply Follow Share https://gateoverflow.in/996/gate2006-33 refer to this ! i think this is the last proof i have! :p see option a only! 1 votes 1 votes MiNiPanda commented Aug 11, 2018 reply Follow Share Yes thank you arvin :D 0 votes 0 votes Please log in or register to add a comment.