wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> RegEx: reverse(L) 
        
(Message started by: Dudidu on Oct 27^th, 2003, 9:22am)

Title: RegEx: reverse(L)
Post by Dudidu on Oct 27^th, 2003, 9:22am

Let L be a regular language. Show that the following language is also regular.

reverse(L) = { xy : yx [in] L}

Hint:[hide] You can look at the RegEx:half(L) thread in the CS section for hints and an example (e.g. my solution) how these kind of problems can be formally solved.[/hide]

Title: Re: RegEx: reverse(L)
Post by towr on Oct 27^th, 2003, 9:45am

I'd call it rotation(L), rather than reverse(L).. (since it isn't really reversing much)
And I think that's allready somewhere in this forum..

[e]of course William has his own ideas, and he called it Cycle(L) (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1053560793)[/e]

Title: Re: RegEx: reverse(L)
Post by Dudidu on Oct 28^th, 2003, 12:02am

on 10/27/03 at 09:45:05, towr wrote:

And I think that's allready somewhere in this forum..

towr you are right ! (I'm so embarassed :-[ recycling problems)
So, Lets change it a little bit... Let L be a regular language. Show that the following language is also regular.

reverse(L) = { w : w^R [in] L}

* If w = x₁x₂...x_n then w^R = x_nx_n-1...x₁.

Quote:

I'd call it rotation(L), rather than reverse(L).. (since it isn't really reversing much)

towr, now you can see that un-intensionally I choose the right name for the thread ;).