##### Are the languages regular ?

{ww^rx ∣ x, w ∈ {0, 1}+ }, {wxw^r ∣ x, w ∈ {0, 1}+ }, {xww^r ∣ x, w ∈ {0, 1}+ } is the above three languages regular ?

Shobhit
28 Oct 2016 07:00 am

first  is not regular...because u have to keep count of when w ended and w^r started...its not possible without a stack
second is regular because u can expand x to cover everything leaving just first and last symbol...its regular expression will be like
0(0+1)*0+1(0+1)*1
third is similar to first...not regular u cant keep track of w and w^r

sujit
28 Oct 2016 02:55 pm

but for ww^rx we can write the regular expression as 00(0+1)*+11(0+1)* correct me if wrong... using the same logic used as for wxw^r

Arjun
28 Oct 2016 01:42 pm

1st is CFL but not dcfl (non regular)

2nd is regular regular experssion for this is 0(0+1)+0 + 1(0+1)+1

3rd is CFL but not dcfl (non regular)

sujit
28 Oct 2016 02:55 pm

but for ww^rx we can write the regular expression as 00(0+1)*+11(0+1)* correct me if wrong... using the same logic used as for wxw^r

Arjun
28 Oct 2016 03:13 pm

see what are you doing wrong first you should understand why wxwr when x,w=(0,1)+ regular expression is 0(0+1)+0 + 1(0+1)+1 is

see if we take w=100 then wr will be 001  or if w=01 then w wil be 10

for first case 100 x 001

for second case 01 x 10

either string "starts with 1 and ends with 1" or "start with 0 and ends with 0"

or we can manipulate it as " 0 anything 0 + 1 anything 1"  because x belongs to (0+1)+

sujit
28 Oct 2016 03:41 pm

understood now.. thanks