The Gateway to Computer Science Excellence
+3 votes

is the language WXWR is regular? can any one provide the proof?

in Theory of Computation by (161 points) | 1.7k views
in such type of questions always include the alphabet set because for different alphabets set answers will be different...
what about on the same Qn with the alphabet set (a,b)+ ?
i will put once W=a x=anything and W=b X=anything for example w1=abababbba w2=babbabaabbb both are accepted

2 Answers

+11 votes
Best answer

WXWis 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 :

by Boss (10.4k points)
selected by

According to you if  W=101  X=100  then  W^R=101

The string is 101100101

but if i pass the string 100100101 which starts and  ends  with but doesn't follow the language.

Always only first character will be considered for W and if this string ends with same character then it should be accepted and otherwise rejected.

In your above 1st example you can assume like - W = 1, X = 0110010, W' = 1.

And in your 2nd example- L= 100100101, W = 1, X = 0010010, W'= 1.

given alphabet set over {0,1}+ then we can take W as 101 also.


yes, you can, but not necessary. You can also take W as 10 but In every case first charecter must have to match with last character of string to get accepted by the FA, then only we can get W and W'. 

i too have the same doubt
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 this language its not saying what is x or how many symbols are x 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 w is not given or length of w or x is not we can assume this way
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 ???
+4 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..
by Boss (14.4k points)
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}+.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,648 questions
56,459 answers
100,192 users