4 votes 4 votes $L = \left \{ a^nb^n \ ; n\geq 0 \ , n \neq 20 \right \}$ is (a) a DCFL (b) a recursive set but not CFL (c) a CFL but not DCFL (d) not a CFL Theory of Computation theory-of-computation closure-property context-free-language + – dd asked Aug 17, 2016 • retagged Jul 4, 2017 by Arjun dd 1.3k views answer comment Share Follow See all 21 Comments See all 21 21 Comments reply dd commented Aug 17, 2016 reply Follow Share $\\ L_1 = \left \{ a^nb^n \ ; n\geq 0 \ \right \} \\ \\ L_2 = \left \{ a^{20}b^{20} \right \} \\$ So, $\\ L = L_1 \ - L_2 \\ \\ L = L_1 \cap \bar L_2$ $L_1$ is DFCL and $\bar L_2$ is Regular (although inf) So from closure property L should be DCFL. Any other way to show that L is indeed DCFL ? or if NOT a DCFL then what ? 4 votes 4 votes ManojK commented Aug 17, 2016 reply Follow Share yes of course $DCFL$ 3 votes 3 votes dd commented Aug 17, 2016 reply Follow Share ans sir, $L = \left \{ a^nb^n \ ; n\geq 0 \ , n \ is \ not \ miltiple \ of \ 3 \right \}$ ? Please show a construciton to show it as DCFL ? 1 votes 1 votes ManojK commented Aug 18, 2016 reply Follow Share Sorry i dont know exact DPDA for it .I only prove this language is DCFL using clousure property. If you know pls add. 0 votes 0 votes dd commented Aug 18, 2016 reply Follow Share No sir by construction i meant formal way of proving it as dcfl, indirectly using closure property, i tried but couldn't. 0 votes 0 votes ManojK commented Aug 18, 2016 i edited by ManojK Aug 18, 2016 reply Follow Share Actually This is same as you proved same above. $L=\left \{ a^nb^n \right \}\cap \left \{ \sum ^*-w| w\ is\ made\ of\ a\ and\ b\ and\ w\ is\ not\ multiple\ of\ 3\right \}$. Which is nothing but DCFL with regular intersection .Which will be DCFL 0 votes 0 votes vijaycs commented Aug 18, 2016 reply Follow Share Check this please- 1 votes 1 votes dd commented Aug 18, 2016 i edited by dd Aug 18, 2016 reply Follow Share So, here the PDA only checks for $n_a \neq 3k$ where k > 1 and. Upper layer doing $n_a(w) \mod 3 \neq 0$. and pushing every 'a' it reads. Reading b from $n_a(w) \mod 3 = 0$ state is invalid and puts us in the trap state.From last two states of upper layer we can start readinng b (which is valid, $n_a(w) \mod 3 = 1,2$ states) , and after reading one b and one pop() we change state and come to a new state. Here we eat up all b's untill stack empty. Now,in this situation, If input is also finished => accepted. [ $n_a(w) == n_b(w)$ and automatically $n_b(w) \neq 3k$ , both requirement ok !!! ] if still more a or b remains trash it to trap state. => rejected. [ although you have only checked for remaining b. but thats ok ! ] is this logic that you have applied ? I think correct !! And Thanks !!! 0 votes 0 votes dd commented Aug 18, 2016 reply Follow Share And Do we really need state D ? 0 votes 0 votes Kapil commented Aug 18, 2016 reply Follow Share @vijay, will it accept abb and aab...? 1 votes 1 votes dd commented Aug 18, 2016 reply Follow Share @Kapil I think No, would not accept those two. I think construction is such a way that, only way to accept something is to have stack empty and input empty.($(\epsilon \ , z_0 \ ,\epsilon )$) transition. 0 votes 0 votes Kapil commented Aug 18, 2016 reply Follow Share For abb -> push a, pop a for one b , and still one b is left. and then it goes to final state, rt? 0 votes 0 votes dd commented Aug 18, 2016 reply Follow Share I see the following way : "still one b is left. and then it goes to final state, rt?" still one 'b' left means we are now going to read b, and also see the stack, found stack $Z_0$ (empty) But ( $b,Z_0,\epsilon$ ) transition goes somewhere else, it is not leading to final state. Am i correct ? or assuming something wrong ? 0 votes 0 votes Kapil commented Aug 18, 2016 reply Follow Share exactly, now apply same logic to aab.. 0 votes 0 votes dd commented Aug 18, 2016 reply Follow Share exactly what ? you mean aab accepted ? 0 votes 0 votes Kapil commented Aug 18, 2016 reply Follow Share how to reject aab? 0 votes 0 votes dd commented Aug 18, 2016 i edited by dd Aug 18, 2016 reply Follow Share In DPDA we can leave some edges undefined as long as non-deterministic nature does not arise. if you see "aab" 'a' push() [ now stack has a ] 'a' push() [now stack has aa ] 'b' pop() [ now stack has a] Now input finished => reading null => expected transition ($\epsilon \ , a , something$) leading to reject state ? correct ? as matter of fact we dont have/or the PDA does not have such transition. That means a DEAD end. That's how aab is rejected. 0 votes 0 votes vijaycs commented Aug 18, 2016 reply Follow Share @kapil , I have forgotten to mention one move.. (€,a, €) should go to dead state ... right ?? 1 votes 1 votes ManojK commented Aug 18, 2016 reply Follow Share Coming to maching described above logic is somewhat correct but yes dead state is unnecessary used here . @Arjun sir and @Praveen sir pls check PDA described above and make it correct. 1 votes 1 votes dd commented Aug 18, 2016 reply Follow Share And no need to provide transition (x,y,z) in some state , where we are sure that if that particular input(x) and stack(y) combination arise, it's going to be rejected. is it corerct ? @ManojK 0 votes 0 votes ManojK commented Aug 18, 2016 reply Follow Share yes of course . Simple languge a^nb^n |n>1 in which b should not come before a. 1 votes 1 votes Please log in or register to add a comment.
2 votes 2 votes the answer is option (A) DCFL see the link given below for explanation : https://gateoverflow.in/63645/toc?merged=25507 jaiganeshcse94 answered Aug 22, 2016 jaiganeshcse94 comment Share Follow See all 0 reply Please log in or register to add a comment.
–1 votes –1 votes option A it is DFCL because you can make a DPDA how?? you have to take large number of states and reject the n=20 case Shubham Pandey 2 answered Sep 9, 2016 Shubham Pandey 2 comment Share Follow See all 0 reply Please log in or register to add a comment.