The Gateway to Computer Science Excellence
+1 vote
How to check whether the language is regular or not ? { wxw | w,x belongs to (a+b)raise to +}
in Theory of Computation by (37 points) | 113 views
it is regular can check by giving the regular expression for is same as a$(a+b)^{+}$a +b($(a+b)^{+}$b,a($(a+b)^{+}$b,b$(a+b)^{+}$a..

this is not regular.

wxw. Let W=01   X= 100

wxw= 01 100 01.Since there is no mention about the lentgh of X,we try to match elements as many as we can to make it regular.In worst case , even if you go till last but one, LHS has 0 and RHS has 1. W  cant take two different values 0,1.

If it had been WXW^R  IT is regular.


2 Answers

+1 vote

It is regular.

Lets see the strings in L
= { a, b, aa, ab, ba, bb, aaa, ..... } (When w is ϵ, wxw generates all these strings and hence we don't need to consider any other case for w)
= Σ* - {ϵ}
As we have no restriction on the length of x, we can leave 1st and last symbol as it is and consider the rest part as x.

eg : w=bab x=bb

wxw = babbbbab; we may assume x = abbbba so we can read it as : bxb which is finite.


by Active (2.3k points)
edited by
atleast first symbol  and last symbol should be matched
w is not ϵ. check w belongs to (a+b)+
but what if w=10?
@basant :

01 001 01 ?

how to match this?
.W=01 and X=001 and last two symbol match with 01.but what happen when string is like 0001111 then i think it can't satisfy the condition of  it is not regular language.
in this case ,we match only first symbol. i.e 0 match with with 0.
it is wxw not wxwr 0r wrxw...

and x is not (a+b)*... i dont think we will have a regular language here.!
@ arvin ,you are correct it's not a regular language.for ex take string=000111,0011,10,1100,111000 does not satisfy the condition of WXW.
I think it should not   be regular as we have flexibility  in managing  x and  But keeping that first and last symbol would not be same when we take w =ab it would satisfy the regular expression
yes it aint :)
0 votes
$a(a+b)^+  a +b(a+b)^+b+ ab(a+b)^+ab+ ba(a+b)^+ba $
by Loyal (5.9k points)

Related questions

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,737 questions
57,292 answers
104,919 users