1 votes 1 votes All DCFL are LL(1) and all LL(1) are LR(1) can someone explain why and how A_i_$_h asked Sep 24, 2017 A_i_$_h 1.8k views answer comment Share Follow See all 43 Comments See all 43 43 Comments reply Manu Thakur commented Sep 24, 2017 reply Follow Share I don't think so that, the statement "All DCFL are LL(1) " is correct. 1 votes 1 votes Rupendra Choudhary commented Sep 24, 2017 reply Follow Share All DCFL are LL(1) : false S-> a|ab DCFL but not LL(1) as LL(n) can't have left recursion,left factoring , ambiguity.... LL(n) is subset of LR(n)... every LL(1) is certainly LR(1) 1 votes 1 votes Arjun commented Sep 24, 2017 reply Follow Share @Rupendra You gave a grammar and showed that it is not LL(1). To prove the first statement you should show that for some DCFL, we cannot make a LL(1) grammar. 1 votes 1 votes Rupendra Choudhary commented Sep 24, 2017 reply Follow Share Even i did same mistake days before when by the same idea i proved 'every regular language is LL(1)' a false statement, which was actually true.Now where did i go wrong , i got it. Thank you sir for paying attention, i'll rectify and prove later as well, if i can. 1 votes 1 votes srestha commented Sep 24, 2017 reply Follow Share Accha think about this grammar S->aSb|aSc|d this is a DCFL but not LL(1) Where is it wrong? 0 votes 0 votes Shubhanshu commented Sep 24, 2017 reply Follow Share L = ${a^{n+m}b^nc^m} \bigcup {d}$ 0 votes 0 votes Rupendra Choudhary commented Sep 24, 2017 reply Follow Share Hello srestha To prove a language ambiguous , you have to prove that we can't generate a single un-ambiguous grammar for the language.. In the same sense , to prove that a every DCFL is not LL(1) prove that for some DCFL no LL(1) possible.... if you show for a particular DCFL , your taken grammar is not LL(1) doesn't mean there wont be any LL(1) for your taken DCFL... 1 votes 1 votes A_i_$_h commented Sep 24, 2017 reply Follow Share yeah its kinda clear.. But the statement says ÄLL DCFL ARE LL(1) so one dcfl is shown which not LL(1) then its wrong statement right 0 votes 0 votes srestha commented Sep 24, 2017 reply Follow Share @Rupendra See U have taken a single string for a grammar to prove ambiguous or not Here it is not the same same case. Here it is told " All DCFL are LL(1) " if we put negation in it by mathematical logic See what happens " All DCFL are LL(1) " i.e.$\forall \left ( DCFL\left ( x \right )\rightarrow LL1\left (x \right ) \right )$ Now putting negation before $NOT\forall \left ( DCFL\left ( x \right )\rightarrow LL1\left (x \right ) \right )$ $\exists \left ( notnotDCFL\left ( x \right )\Lambda not LL1\left (x \right ) \right )$ that means $\exists \left ( DCFL\left ( x \right )\Lambda not LL1\left (x \right ) \right )$ Which means there exists some DCFL which are not LL(1) So, if we can show atleast one language which are DCFL but not LL(1), that disproves " All DCFL are LL(1) " If anything is wrong feel free to correct me plz 1 votes 1 votes Arjun commented Sep 24, 2017 reply Follow Share @srestha Nice proof and way of thinking :) But the point here is what is LL(1)? A language becomes LL(1) if it has an LL(1) grammar. It may or may not have a non-LL(1) grammar, as multiple grammars are possible for a given language. 0 votes 0 votes Rupendra Choudhary commented Sep 25, 2017 reply Follow Share Hello srestha , nice try , there is nothing wrong with your logic but what i'm saying is showing any particular grammar that generate DCFL and that is not LL(1) doesn't prove we can't have any LL(1)grammar , may be your chosen grammar is not LL(1) but may be for this DCFL there is another LL(1) possible....A language can be generated by many grammars like take my own example i took S->a|ab i said it's generating Regular language so DCFL too and as it's a left factored grammar so it's not LL(1) ...but this doesn't mean there won't be any LL(1) as left factoring can be removed like for above DCFL LL(1) grammar is S->aA A->b|∊ am i wrong somewhere ? 0 votes 0 votes Shubhanshu commented Sep 25, 2017 reply Follow Share @Arjun Sir, For Your first comment, To prove the first statement you should show that for some DCFL, we cannot make a LL(1) grammar. I have this DCFL = $(a^nb^n)\bigcup(a^{n+1}b^n)$ And DCFG for this:- S -> aSb/aAb A-> aAb Now it is DCFL but not LL(1) Even if we try to do left factoring we get S -> aS' S' -> Sb/Ab A -> aAb Even after doing left factoring we are not getting LL(1) So, I think All DCFL are LL(1) is false. Correct me if I am wrong!!!! 0 votes 0 votes Rupendra Choudhary commented Sep 25, 2017 reply Follow Share (anbn)⋃(an+1bn) : Not DCFL 0 votes 0 votes Shubhanshu commented Sep 25, 2017 reply Follow Share @Rupendra Choudhary No, it is DCFL. Check DPDA for this:- ..... 2 votes 2 votes Arjun commented Sep 25, 2017 reply Follow Share @Shubhanshu Yes, it is DCFL. But you should see all possible grammars for it -- which is not possible. You may be correct that this language is not LL(1) -- I do not remember exactly the condition to prove this. LR(1) generates strictly the class of DCFLs. 0 votes 0 votes Shubhanshu commented Sep 25, 2017 reply Follow Share Sir, I have read somewhere that LR(K) enclose LL(k), But because of above statement I have Consider DCFL also. is it correct let me know???!!! 0 votes 0 votes Arjun commented Sep 25, 2017 reply Follow Share Don't think so -- I'll confirm though. 0 votes 0 votes A_i_$_h commented Sep 25, 2017 reply Follow Share where are you checking the condition for b after Union (U) ??? 0 votes 0 votes Shubhanshu commented Sep 25, 2017 reply Follow Share When it have a = b then q1 to q3 When it will have a = b+1 then q1 to q2 to q3. 0 votes 0 votes A_i_$_h commented Sep 25, 2017 reply Follow Share okay then seee an bn is checked then your checking an+1 after that the number of b's can be anything according to the pda..but it should be bn right 0 votes 0 votes Rupendra Choudhary commented Sep 25, 2017 reply Follow Share DCFL yes shubhanshu ,sorry. I had just in mind if first for n a's n b are to pop then for n+1 b's n a's..so there it have to make choice which DCFL can't do but actually there is only one choice we have to make pop n a's for n b's ....thanks for correcting me... For every DCFL , we have some LR(k) to generate it , but we may not have LL(k) to generate every DCFL.... i don't think your diagram is correct .... as i know every DCFL is LR(1) and every LR(k) is DCFL. deterministic context-free languages are the same as LR(1) languages. http://planetmath.org/lrk#Thmthm1 0 votes 0 votes A_i_$_h commented Sep 25, 2017 reply Follow Share ya correct..got it :) even i considered it the same way as u did @rupendra...thats why thought it to not be a DCFL 0 votes 0 votes A_i_$_h commented Sep 25, 2017 reply Follow Share i think that if it was not Union and it was concatenation then it would not be a DCFL 0 votes 0 votes Rupendra Choudhary commented Sep 26, 2017 reply Follow Share even {anbn } ∪{an+kbn} would be DCFL no anbnan+1bn is DCFL too..... 0 votes 0 votes Shubhanshu commented Sep 26, 2017 reply Follow Share @Rupendra Choudhary how an+kbn this one is DCFL, before giving it to DPDA you should know the value of k. right?? And anbnan+1bn is DCFL too..... if only n is used. but what about ambman+1bn ..... but this one is not dCFL when m>=0 , n >=1 0 votes 0 votes A_i_$_h commented Sep 26, 2017 reply Follow Share how please exaplain... no anbnan+1bn is DCFL too..... check for equal a's and b's then for an extra a and then what about the b's after that? 0 votes 0 votes Shubhanshu commented Sep 26, 2017 reply Follow Share for first occurence of a push it into the stack and for first occurrence of b pop those a's present in the stack as soon as last b reads only one a will be in the stack which was also poped out, now again do same push all a's into the stack and pop a's when b comes at last when you have only one a in the stack pop that a also and accept the string. 0 votes 0 votes A_i_$_h commented Sep 26, 2017 reply Follow Share okay lets consider a2 b2 a4 b3 now push a's and pop when b's come one extra a is popped now push 3a's and pop with the b's this is accepted right but it isnt an bn an+1 bn 0 votes 0 votes Rupendra Choudhary commented Sep 26, 2017 reply Follow Share @aish; You didn't focus carefully shubhansu's PDA...look at one more time an.ak.bn // match n no of a with n no of b and then there would left k a's in stack , pop k time through q4.....here k is constant independent of n There is one popular DCFL , hope you faced it before anbncmdm // same concept first push pop with a ,b then push pop with c,d push pop quite clear for DPDA so DCFL... 0 votes 0 votes srestha commented Sep 26, 2017 reply Follow Share Again one miss in concept I think @Shubhanshu $(a^nb^n)\bigcup(a^{n+1}b^n)$ cannot be DCFL, Because if u push n no. of a's and then pop n no. of b's. Now how will u push n no. of a's? It is not possible. If u want to push exactly n a's , u must have to take a counter for it. Otherwise u cannot push exactly n a's again. yes, in NCFL it is possible 0 votes 0 votes Shubhanshu commented Sep 26, 2017 reply Follow Share @srestha, are you talking about an bn an+1 bn where we are using n only, yes this one is not CFL. But if you are talking about the language which you mentioned in the comment then check DPDA for this. 0 votes 0 votes srestha commented Sep 26, 2017 reply Follow Share Can u tell me one thing $a^{n}b^{n}a^{n}$ is it a DCFL? 0 votes 0 votes srestha commented Sep 26, 2017 i edited by srestha Sep 26, 2017 reply Follow Share Though I think u r drawn a pda for $a^{n}b^{n}\cup a^{n}b^{n}a^{n}$ only 0 votes 0 votes Shubhanshu commented Sep 26, 2017 reply Follow Share @srestha Can u tell me one thing anbnan is it a DCFL? A BIG NO. For second one, See the DPDA carefully, formate is {input, TOS/ Action} after seeing b's it is no where mention in the DPDA that we will see a's again. 0 votes 0 votes srestha commented Sep 26, 2017 reply Follow Share @Shubhanshu That is the biggest reason to say your drawn PDA is not a DPDA because a PDA divide in 2 path , we can say it is certainly a NCFL Never can be DCFL 0 votes 0 votes Shubhanshu commented Sep 26, 2017 reply Follow Share you should consider both input symbol and TOS, Because based on these two factor only DPDA decide what to do next. 0 votes 0 votes Shubhanshu commented Sep 26, 2017 reply Follow Share first one is {ep , z0} and second one is {ep, a} then how these are same? 0 votes 0 votes srestha commented Sep 26, 2017 i edited by srestha Sep 26, 2017 reply Follow Share yes, it is not same, that was wrong but ur PDA is only $a^{n}b^{n}\cup a^{n}b^{n}a^{m}$ which cannot be represented by one stack If u think it can be represented by one stack, explain in words 0 votes 0 votes Manu Thakur commented Sep 26, 2017 i edited Sep 26, 2017 reply Follow Share Can someone please tell me how can I stop notification for this question? :( :( it's difficult to handle now, a few more notifications on this post :( 0 votes 0 votes Shubhanshu commented Sep 26, 2017 reply Follow Share @srestha through I am not saying given Dpda accept anbnan . I am saying that it will accept an+1bn I think you are interpreting in wrong way. 0 votes 0 votes srestha commented Sep 26, 2017 reply Follow Share an+1bn yes DPDA Don't mind :) but how my interpretation wrong? 0 votes 0 votes Shubhanshu commented Sep 26, 2017 reply Follow Share I thought you were considering anbnan in the language. 0 votes 0 votes srestha commented Sep 26, 2017 reply Follow Share Can we say from here that 1st statement is False https://gateoverflow.in/105785/ll-k-grammars 0 votes 0 votes Please log in or register to add a comment.