Log In
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 152 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.


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 $

Related questions

0 votes
2 answers
0 votes
1 answer
Consider the following language: L = {w| w $\epsilon$ {0,1}* ; w has equal number of occurances of 001' and 010' } The solution they provided: The absolute difference between the number of occurrences of 001' and 010' is at most 1. Hence a DFA can be found. I ... going to find an occurrence of 010' (and vice-versa)). But, since such info is not given, so how this can be a regular language?
asked Jan 29, 2019 in Theory of Computation Harsh Kumar 116 views
0 votes
0 answers
Which of the following option is correct regarding dependability? A. Given a regular language R and context-free C. Is every string in R also in C, i.e., Is L(R)⊆L(C) decidable? B. Given a regular language R and context-free C. Is every string in C also in R, i.e., Is L(C)⊆L(R) decidable? C. Both (A) and (B) D. None of these
asked Jan 7, 2019 in Theory of Computation Shivangi Parashar 2 49 views