3 votes 3 votes is the language WXWR is regular? can any one provide the proof? RRajeev asked Jun 29, 2015 RRajeev 7.8k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Bhagirathi commented Jun 29, 2015 reply Follow Share in such type of questions always include the alphabet set because for different alphabets set answers will be different... 3 votes 3 votes RRajeev commented Jun 29, 2015 reply Follow Share what about on the same Qn with the alphabet set (a,b)+ ? 0 votes 0 votes Bhagirathi commented Jun 29, 2015 reply Follow Share i will put once W=a x=anything and W=b X=anything for example w1=abababbba w2=babbabaabbb both are accepted 0 votes 0 votes Uditkumar13 commented Sep 1, 2020 reply Follow Share LET L = WxW$^{R}$ , constraints : W ϵ (a+b)* , x ϵ (a+b)$^{+}$ , Generally L is a odd length palindrome if x ϵ {a,b} which makes it a CFL but here x ϵ (a+b)$^{+}$ lets take the example W=abbab, W$^{R}$= babba and x = bbbb so L = abbabbbbbbabba so if you closely look at this new string L , see the first letter and last letter, we can say that it will always starts and ends with the same letter and in between we can have anything so actually L can be expressed as L =a(a+b)$^{+}$a + b(a+b)$^{+}$b , which can be expressed by dfa so it become regular language . So point to be remember while solving question look closely on constraints given and try making it a regular lang, if it can be expressed in any dfa then it is regular else choose the best option left. 0 votes 0 votes Please log in or register to add a comment.
Best answer 12 votes 12 votes WXWR is regular on {a,b} . X can be anything . so we can rewrite this language as " starting bit and ending bit are same " which is a regular language . Here, If alphabet set = (a,b)+, Then , Language accepted by the finite automata, L = a(a+b)+a + b(a+b)+b . see this : http://stackoverflow.com/questions/14521300/why-l-wxwr-w-x-belongs-to-a-b-is-a-regular-language Pranay Datta 1 answered Jun 29, 2015 • selected Sep 27, 2016 by vijaycs Pranay Datta 1 comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments Jagannath Prasad Das commented Apr 4, 2018 reply Follow Share i too have the same doubt 0 votes 0 votes Sufayya commented Jul 5, 2018 reply Follow Share if your question was in the category which says x is bounded.. then |x|=3, so its not regular.. but the question says x is unbounded , we can treat this entire language as starting and ending with same symbol.. then we will assume w and reverse of w as the first and last symbol. so here w=1(fst) and w^r =1(last symbol)..remaining all will be x ..in this language its not saying what is x or how many symbols are x ..so we have the provision to make everything except first and last to be x.. but if it was given that |x|=3' then it will not be regular..here w is not given or length of w or x is not given..so we can assume this way 0 votes 0 votes None ... commented Dec 31, 2018 reply Follow Share as far i know a finite automata can accept a string which is in the language as well as can reject a string which is not in the language.... then how can it be regular ?? can anyone clarify me ??? 0 votes 0 votes Please log in or register to add a comment.
5 votes 5 votes i assume W,X belongs to {a,b}* i will always intentionally put W=null and X=string you provide me now X belongs to {a,b}* so the whole language is regular.. Bhagirathi answered Jun 29, 2015 Bhagirathi comment Share Follow See 1 comment See all 1 1 comment reply commenter commenter commented Dec 6, 2018 reply Follow Share What if w is null? The language becomes ww^R which is not regular. So I think it is Regular only if x is {a,b}+. 0 votes 0 votes Please log in or register to add a comment.