##### Regular Language

Which of the following is regular language?

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

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

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

d. All of these.

Which of the following is regular language?

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

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

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

d. All of these.

ANS=D

Explain.

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

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

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.

only B is regular

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

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.

## Pages