2 votes 2 votes Is L = {a bn an ;n > 0} $\cup${aa bk a2k ;k > 0} a DCFL ??? User007 asked Oct 3, 2016 edited Oct 3, 2016 by srestha User007 557 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply srestha commented Oct 3, 2016 reply Follow Share yes it is DCFL 2 votes 2 votes User007 commented Oct 3, 2016 reply Follow Share Could you please explain your answer. 0 votes 0 votes Please log in or register to add a comment.
Best answer 4 votes 4 votes L = {a bn an ;n > 0} ∪∪{aa bk a2k ;k > 0}. DCF Grammar for generating above language -> S -> aT T - > aU | bV U - > bUaa | baa V - > bVa | a DPDA for accepting above language -> vijaycs answered Oct 3, 2016 selected Oct 3, 2016 by Kapil vijaycs comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments srestha commented Oct 4, 2016 reply Follow Share @vijay @Kapil Both part are DCFL. DCFL not closed under union. So, result may or may not be DCFL. Now, it is starting with DCFL format. But at end can we confirm it is DCFL? Say, S->aSbb | aSbbb |$\epsilon$ is it DCFL? 0 votes 0 votes vijaycs commented Oct 4, 2016 reply Follow Share @srestha, Here in this particular case it seems like it is union of 2 DCFL, but it is not so... you can check above DCFG and DPDA, ... if you find any problem in that then please let me know... Now coming to your exampe - S -> aSbb | aSbbb | ϵ L = anbm , where n >0 , 2n=<m <= 3m. rt ?? And I think, it is not even CFL right ?? Can we implement an PDA with 1 stack ?? I don't think we can ... 0 votes 0 votes . commented Oct 5, 2016 reply Follow Share in the above given implementation for an a we will either push 2 b's or 3 b's then why it cannot be an ncfl. 1 votes 1 votes Please log in or register to add a comment.