wu :: forums « wu :: forums - RegEx: reverse(L) » Welcome, Guest. Please Login or Register. Feb 5th, 2016, 11:01pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    cs (Moderators: Eigenray, william wu, Grimbal, SMQ, Icarus, towr, ThudnBlunder)    RegEx: reverse(L) « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: RegEx: reverse(L)  (Read 2824 times)
Dudidu
Full Member

Posts: 227
 RegEx: reverse(L)   « on: Oct 27th, 2003, 9:22am » Quote Modify

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

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

Hint: 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.
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13294
 Re: RegEx: reverse(L)   « Reply #1 on: Oct 27th, 2003, 9:45am » Quote Modify

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)[/e]
 « Last Edit: Oct 27th, 2003, 9:48am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Dudidu
Full Member

Posts: 227
 Re: RegEx: reverse(L)   « Reply #2 on: Oct 28th, 2003, 12:02am » Quote Modify

on Oct 27th, 2003, 9:45am, 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 : wR [in]  L}

* If w = x1x2...xn then wR = xnxn-1...x1.

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 .
 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »