The Gateway to Computer Science Excellence
+3 votes
1.7k views

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

in Theory of Computation by (161 points) | 1.7k views
+3
in such type of questions always include the alphabet set because for different alphabets set answers will be different...
0
what about on the same Qn with the alphabet set (a,b)+ ?
0
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 : http://stackoverflow.com/questions/14521300/why-l-wxwr-w-x-belongs-to-a-b-is-a-regular-language

by Boss (10.4k points)
selected by
0

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.

0
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.
0

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

0

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'. 

0
i too have the same doubt
0
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
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)
0
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
195,337 comments
100,192 users