Author |
Topic: Cycle(L) (Read 9578 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
Consider a language L. Now consider the language CYCLE(L), which consists of all cyclic permutations of strings in L. So for example, if L = { ab, aaab }, then CYCLE(L) = { ab, ba, aaab, aaba, abaa, baaa }.
If L is a regular language, is CYCLE(L) a regular language as well? If so, justify with a construction. If not, prove it.
Note 1: A language is regular if it can be realized by a regular expression, or equivalently, a deterministic finite automaton (DFA), or equivalently, a nondeterministic finite automaton (NFA).
Note 2: Formal definitions of DFAs and NFAs; P(Q) denotes power set of Q:
Problem Source: UC Berkeley CS172 (Computability and Complexity Theory) Final Exam, Spring 2003
|
| « Last Edit: May 21st, 2003, 5:22pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
 |
Re: Cycle(L)
« Reply #1 on: May 21st, 2003, 11:50pm » |
 Quote  Modify
|
on May 21st, 2003, 4:46pm, william wu wrote:
If L is a regular language, is CYCLE(L) a regular language as well? |
|
I think so.
And I have some idea as to how to do it, I just have to figure out how to explain it properly..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Papa Homer
Guest
|
Cycle(L) is not regular.
Let L = {a2nb}. Then Cycle(L) = {a2n-kbak}. Clearly L is a regular language (I can describe a DFA for it if it is not clear). However, Cycle(L) is not. Intuitively, Cycle(L) requires us to keep state that growth with the length of the input which is kind of hard to do when you only have "finite state." Formally, we can use the Pumping Lemma to prove this (which I am too lazy to do unless there is sufficient interest).
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Cycle(L)
« Reply #3 on: May 28th, 2003, 1:44pm » |
Quote Modify
|
correct me if I'm wrong
L = {a2nb} means you have any even number of a's and then one b, right?
so L = [[a,a]*,b]
so Cycle(L) would be either any even number of a's followed by one b and any even number of a's again, or any uneven number of a's followed by one b and any uneven number of a's.. Seems very regular to me.
Cycle(L) = {[[a,a]*,b,[a,a]*] , [a, [a,a]*,b, a, [a,a]*] }
(notation as used for http://odur.let.rug.nl/~vannoord/fsademo/ )
|
| « Last Edit: May 28th, 2003, 2:05pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Cycle(L)
« Reply #4 on: May 28th, 2003, 6:07pm » |
Quote Modify
|
Cycle(L) is regular if L is regular. To justify this, the hint is to use nondeterminism to make the construction. Given a DFA, make an NFA that realizes Cycle(L).
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
xlh
Guest
|
Given DFA D = (Q={q1 ... qn},A,q1,F) which accepts language L(D), NFA N = ({q*} + (Q+Q') x Q,A,q*,F') will accept CYCLE(L(D)). For each state in qi in Q, N will have states corresponding to 2 copies of Q, call them Qi and Qi'. Denote the jth state in Qi by qij and the jth state in Qi' by qij'. Keep all the transitions from D within each of these copies. Add epsilon transitions {(q* -> qii) : qi in Q} and {(qij -> qi1') :qj in F}. Define F' = {qii': qi in Q}.
Essentially we're running |Q| copies of D in order to "guess" where in the cycle we should start. The doubling into Q and Q' parts ensures that the cycle we are matching does pass from start state to a final state in the original D.
For any word uv in L(D), let qk be the state of D after processing u. Then reading v would cause a transition from qk to some state in F. On reading the string vu, N will go from q* to qkk by epsilon move, then reading v will lead to some state qkj where qj in F, then by epsilon to qk1', then by reading u to qkk'. So CYCLE(L(D)) is a subset of L(N)
For any word z in L(N) let qkk' be one of the final states which is active after reading z. Since all paths from q* to qkk' pass through a transition qkj -> qk1' for some qj in F, pick some partition of z=vu such that one of these epsilon transitions occurs between v and u in a path leading to the accepting state qkk'. This means that D will move from q1 to qk while reading u and from qk to qj while reading v, thus uv in L(D). So, L(N) is a subset of CYCLE(L(D)) and thus L(N) = CYCLE(L(D))
|
|
IP Logged |
|
|
|
kaltik
Newbie
Posts: 1
|
|
Re: Cycle(L)
« Reply #6 on: May 13th, 2012, 6:21am » |
Quote Modify
|
@ last post by XLH:
Thank you for your detailed answer. But i do not understand what "{q*} + (Q+Q') x Q" means.
More precisely, how do you construct the NFA-states?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove