0 0 votes L={wxwR |w belongs to(a+b)* ,x belong to (a+b)} the complement of language L is ???? A)regular B)dcfl but not regular C)cfl but not dcfl D)none of these answer given is c but any example is there please provide?? Theory of Computation + – eyeamgj 1.5k views answer comment Share Follow Print See all 7 Comments 7 7 Comments reply Deepanshu commented Aug 19, 2018 reply Follow flag ANSWER IS C OR D????? I AM GETTING D AS CFL NOT CLOSED UNDER COMPLEMENT AND ABOVE LANGUAGE IS CFL. SO I AM GUESSING IT D 0 0 replyShare MiNiPanda commented Aug 19, 2018 reply Follow flag I also think it is D :/ 1 1 replyShare eyeamgj commented Aug 19, 2018 reply Follow flag WHAT I AM THINKING IS THAT L IS ODD PALINDROME AND WE KNOW IT IS DCFL BECZ WE HAVE CENTER IN THIS .............SO L COMPLEMENT WILL BE EVEN LENGTH PALiNDROMe i.e l=wwR and this is ncfl hence cfl 1 1 replyShare Deepanshu commented Aug 19, 2018 reply Follow flag @eyeamgj YEPP IT IS ODD PALINDROME BUT COMPLEMENT OF ODD PALINDROME IS NOT EVEN PALINDROME. COMPLEMENT IS = ALL SET OF LANGUAGES POSSIBLE - ODD PALINDROME IT WILL ALSO CONTAIN IN WHICH THERE IS NO PALINDROME EVEN AS IT IS COMPLEMENT. FROM MY VIEW 0 0 replyShare eyeamgj commented Aug 19, 2018 reply Follow flag ya but it will contain even palindrome it is sure and no odd length length string it is also sure so why we cant say on thjis basis that it will be ncfl not dcfl?? 0 0 replyShare Kalpataru Bose commented Aug 21, 2018 reply Follow flag it is dcfl answer is B 0 0 replyShare eyeamgj commented Aug 21, 2018 reply Follow flag @ Kalpataru Bose reason?? 0 0 replyShare Please log in or register to add a comment.
1 1 vote S is the start state. S→ aSa | bSb | A | ɛ A→ aBb | bBa B→ aBa | bBb | aBb | bBa | a | b | ɛ Vikas Verma answered Aug 19, 2018 • edited Aug 19, 2018 by Vikas Verma Vikas Verma comment Share Follow 0 reply Please log in or register to add a comment.
