Author |
Topic: RegEx: reverse(L) (Read 3230 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: 13730
|
|
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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print