2 votes 2 votes Which of the following is CFL ? a) L1 is CFL b)L1 is CFL but L2 is not CFL c)Both L1 and L2 are CFL d) None Theory of Computation zeal theory-of-computation identify-class-language zeal2019 + – Prince Sindhiya asked Aug 3, 2018 • edited Mar 9, 2019 by ajaysoni1924 Prince Sindhiya 1.1k views answer comment Share Follow See all 23 Comments See all 23 23 Comments reply Kajal Khobragade commented Aug 3, 2018 reply Follow Share b ? 0 votes 0 votes arvin commented Aug 3, 2018 reply Follow Share yes B 0 votes 0 votes abhishekmehta4u commented Aug 3, 2018 reply Follow Share Both are cfl 0 votes 0 votes arvin commented Aug 3, 2018 reply Follow Share how is the second one a cfl? can u explain 0 votes 0 votes Anand. commented Aug 3, 2018 reply Follow Share $L=\left \{ a^m b^nc^pd^q ,m+p=n+q\right \}$ Conditions can be written as-: $\Rightarrow m+p-n=q$ Now perform following operations on stack Push "a" on seeing "a" pop "a" on seeing a "b" Push "c" on seeing "c" pop "c" OR pop "a" on seeing "D"..here there is non determinism. if stack Empty-:language accepted.! 1 votes 1 votes Shaik Masthan commented Aug 3, 2018 reply Follow Share push x on getting a, pop x on getting b on x, otherwise push y on getting b on ( empty stack or y ) pop y on getting c on y, otherwise push x on getting c on ( empty stack or x ) pop x on getting d on x, if stack is empty, accepted 1 votes 1 votes arvin commented Aug 3, 2018 reply Follow Share @anand what for the string : ab3c3d = m+p=n+q => 4 => it won't accept @shaik Masthan : i don't know whether we can use other symbols in cfg i mean i haven't came across any such solution . u are trying to replace or overwrite the symbols which is only possible for turing machine. 0 votes 0 votes Shaik Masthan commented Aug 3, 2018 reply Follow Share @ arvin, PDA have ∑ = input symbols and Π = stack symbols right ( Π is not exact symbol) my x and y are in Π moreover note that , ∑ ⊂ Π 0 votes 0 votes Prince Sindhiya commented Aug 3, 2018 reply Follow Share Answer is both are CFL , I understood the first one as there is or condition so there will npda for it. But I am not understanding the second one. 1 votes 1 votes Prince Sindhiya commented Aug 3, 2018 reply Follow Share @abhishek can you draw npda for second one or can you give me hint for it . 0 votes 0 votes srestha commented Aug 3, 2018 i edited by srestha Aug 3, 2018 reply Follow Share here both only not CFL ,a)NCFL b)DCFL 0 votes 0 votes Shaik Masthan commented Aug 3, 2018 reply Follow Share @srestha, mam i am not getting how the DPDA form for the L1? 0 votes 0 votes srestha commented Aug 3, 2018 reply Follow Share $S\rightarrow S_{1}S_{2}|S_{3}S_{4}$ $S_{1}\rightarrow aS_{1}b|S_{1}b|\epsilon$ $S_{2}\rightarrow cS_{2}|c$ $S_{3}\rightarrow aS_{3}|\epsilon$ $S_{4}\rightarrow bS_{4}c|bS_{4}|b$ 1 votes 1 votes Prince Sindhiya commented Aug 3, 2018 reply Follow Share @srestha mam if we take the production $S$->$S_3S_4$ Then how it will derive c 0 votes 0 votes Shaik Masthan commented Aug 3, 2018 reply Follow Share @ Prince Sindhiya,mam By using S4, it will generate c @srestha, mam, I agree it is CFL, every CFL has a CFG but my doubt is how it is DCFL, i am not getting it 0 votes 0 votes srestha commented Aug 3, 2018 reply Follow Share @Shaik why r u telling it is not DCFL u mean different path to follow in OR case? 0 votes 0 votes Shaik Masthan commented Aug 3, 2018 reply Follow Share why r u telling it is not DCFL mam, i am not able to draw DPDA 0 votes 0 votes srestha commented Aug 3, 2018 reply Follow Share and for NPDA? 0 votes 0 votes Shaik Masthan commented Aug 3, 2018 reply Follow Share and for NPDA? yes i can,thats why i concluded it is CFL 0 votes 0 votes srestha commented Aug 3, 2018 reply Follow Share yes u right @Shaik https://gateoverflow.in/30669/identify-whether-language-context-free-context-sensitive Similar to C here right? 0 votes 0 votes Shaik Masthan commented Aug 3, 2018 reply Follow Share yes... Finally concluded that L1 is CFL and L2 is DCFL 1 votes 1 votes Prince Sindhiya commented Aug 3, 2018 reply Follow Share Shaik sir , please explain the second one how it is dcfl ? 0 votes 0 votes Shaik Masthan commented Aug 3, 2018 reply Follow Share @ prince mam, push x on getting a, pop x on getting b on x, otherwise push y on getting b on ( empty stack or y ) pop y on getting c on y, otherwise push x on getting c on ( empty stack or x ) pop x on getting d on x, if stack is empty, accepted in this process did you find any ambiguity?? 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes This should be npda for first one Prince Sindhiya answered Aug 3, 2018 Prince Sindhiya comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Answer should be c) Shivani gaikawad answered Aug 3, 2018 Shivani gaikawad comment Share Follow See all 0 reply Please log in or register to add a comment.