0 votes 0 votes is L a regular lang. or CFL ? L={XWWR |w$\epsilon$(0+1)+ ,x$\epsilon$(0+1)+} explain how? hitendra singh asked Sep 30, 2018 hitendra singh 585 views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply hitendra singh commented Sep 30, 2018 reply Follow Share are you sure ? 0 votes 0 votes Swapnil Naik commented Sep 30, 2018 reply Follow Share It is not regular because how you will check WWR , If it would have been WXWR then this could be regular as you can extend X. You can construct NPDA for WWR but then X can include anything, but then how can we differentiate X and W so that we can match with WR . We can bypass X but till what amount that is not sure. like for eg. abbabbbba , hence I don't think it is cfl. 0 votes 0 votes hitendra singh commented Sep 30, 2018 reply Follow Share what you mean by extending X 0 votes 0 votes Swapnil Naik commented Sep 30, 2018 reply Follow Share https://stackoverflow.com/questions/14521300/why-l-wxwr-w-x-belongs-to-a-b-is-a-regular-language 0 votes 0 votes hitendra singh commented Sep 30, 2018 reply Follow Share so similarly why can't we do the same here also let X=(0+1)+ W=a and WR=a or b the also we must accept . Isn't it right ? As per your above comment language should be ending with 2 a's or b's. correct me if I am wrong . 0 votes 0 votes Swapnil Naik commented Sep 30, 2018 reply Follow Share wϵ(0+1)+ it can be more than one letter lets say w= 1010 then wR has to be 0101 now arrange like 1010010101 but they have said that X can be any combination of 0,1 hence I can say that 1010010101, x=01001010 X=(0+1)+ W=a and WR=a this is just a single instance you have considered, also a,b are not allowed if they would have allowed then XWWR would be Cfl such that X=(0+1)+ W=(a+b)+ 0 votes 0 votes hitendra singh commented Sep 30, 2018 reply Follow Share can you make the last line more clear? actually my previous comment was wrong there no a b in the language. 0 votes 0 votes Swapnil Naik commented Sep 30, 2018 reply Follow Share See WWR is CFL, now X is a combination of 0,1. for XWWR bypass all 0,1 and as soon as you encounter a or b then you have to just check WWR which is a cfl. for this you need construct pda which is machine that accepts a cfl language. also lets say x=1100, w=0111 wr = 1110 so now the string will form is XWWR = 110001111110, in this case how will you come to know you need to bypass 1100. you can construct a single pda for above string, but the pda for above grammar should contain all types of string with all combination of 0,1 i.e. it should be universal which I don't think is possible. 010110 is this string acceptable by XWWR - Yes, but the problem is that I don't know from where should I start checking for 0110 as it is WWR . I can't always say for any given string always bypass 01 and then check for 0110. for above string only bypassing 01 is true. 0 votes 0 votes hitendra singh commented Sep 30, 2018 reply Follow Share I have clearly mentioned that there is no a & b in the language but isn't i possible to make Npda . because in Npda you have to go through every possibility if after going through all possibility you don't accept then only you can reject . 0 votes 0 votes Swapnil Naik commented Sep 30, 2018 reply Follow Share yeah I know I was just giving example. 1 votes 1 votes Swapnil Naik commented Oct 1, 2018 reply Follow Share Sorry its not regular but it can be accepted by npda. It is non-deterministic cfl https://gatecse.in/identify-the-class-of-a-given-language/ 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes It is not a CFL. pradeepchaudhary answered Sep 30, 2018 pradeepchaudhary comment Share Follow See all 3 Comments See all 3 3 Comments reply Shubhanshu commented Oct 1, 2018 reply Follow Share No the given language is CFL and is accepted by NPDA. 2 votes 2 votes hitendra singh commented Oct 1, 2018 reply Follow Share can you explain a bit ? 0 votes 0 votes Shubhanshu commented Oct 1, 2018 reply Follow Share It is of the form (0+1)^+ww^r which is CFL. 0 votes 0 votes Please log in or register to add a comment.