##### Regular Language

Which of the following is regular language?

a. L={wxw|w,x∈(a+b)*}

b. L={wxwR|w,x∈(a+b)*}

c. L={xww|w,x∈(a+b)*}

d. All of these.

Satya Prakash @sprp
16 Jan 2016 06:45 pm

ANS=D

lucky
16 Jan 2016 06:50 pm

Explain.

Satya Prakash @sprp
16 Jan 2016 07:00 pm

in wxw or wxw^R w is always single string a or b...

so i am taking example for option b

Language L = {WXWR| x, W ∈ {a,b}+} means:

string should start any string consist of a and b that is W and end with reverse string WR.
notice: because W and WR are reverse of each other so string start and end with same symbol(that can be either a or b)
And contain any string of a and b in middle that is X. (because + length of X grater then one|X| >= 1)

Example of this kind of strings can be following:

aabababa, as follows:

a ababab a -- -------- -- w X W^R

or it can be also:

babababb, as follows:

b ababab b -- -------- -- w X W^R

See length of W is not constraint in language definition.

so any string WXWR can be assume equals to a(a + b)+a or b(a + b)+b

a (a + b)+ a --- -------- --- W X W^R

or

b (a + b)+ b --- -------- --- W X W^R

And Regular Expression for this language is: a(a + b)+a + b(a + b)+b

Don't mix WXWR(regular) with WCWR(not regular), its X with + that makes language regular. Think by including X that is (a + b)* we can have finite choice for W that is a and b (finite is regular).

SIMILARLY FOR OTHERS

meet @meet
16 Jan 2016 07:22 pm

i think Ans is only B

other are not regular...

because in other option we must remember the previous string..

but in option B we just extend the X so it is possible for regular

Anurag Verma
16 Jan 2016 07:28 pm

Ya I also think the answer is B because if we just compare the first and the last characters , we can design the automaton for accepting that language as we can classify everything else as X , as explained by satya above.

Parimal Andhalkar
16 Jan 2016 07:34 pm

only B is regular

Simranjit Singh
3 May 2016 03:41 pm
Thnks for reply but they are also stuck in there pumping lemma is not failing for those strings which should not be accepted.There is nothing about this language anywhere why is this language accepting 10111011???
Satya Prakash @sprp
3 May 2016 03:41 pm
Simranjit Singh
3 May 2016 03:41 pm

I have only one doubt. By doing this regular expression we are accepting the string which are starting and ending with same symbol .

Now if w=101,X=1,WR=1011 It is also accepting which should be wrong i think.

please clear this doubt

Chandan Chawda
5 May 2016 04:45 pm

For the given string, consider X=011101, W=1, W^R=1. It is clear that this is a regular language. W^R means reverse of string W. Reverse of 101 cannot be 1011 :) Since, x belongs to (a+b)*, you can consider WXW^R as a language accepting all the strings where first and last alphabets are same.