wu :: forums - Print Page


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

        riddles >> cs >> Cycle(L)
        
(Message started by: william wu on May 21^st, 2003, 4:46pm)

Title: Cycle(L)
Post by william wu on May 21^st, 2003, 4:46pm

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:

http://www.ocf.berkeley.edu/~wwu/images/riddles/dfa_nfa_definitions.gif

Problem Source: UC Berkeley CS172 (Computability and Complexity Theory) Final Exam, Spring 2003

Title: Re: Cycle(L)
Post by towr on May 21^st, 2003, 11:50pm

on 05/21/03 at 16:46:32, 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..

Title: Re: Cycle(L)
Post by Papa Homer on May 28^th, 2003, 1:23pm

Cycle(L) is not regular.

Let L = {a²ⁿb}. Then Cycle(L) = {a^2n-kba^k}. 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).

Title: Re: Cycle(L)
Post by towr on May 28^th, 2003, 1:44pm

correct me if I'm wrong

L = {a²ⁿb} 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/ )

Title: Re: Cycle(L)
Post by william wu on May 28^th, 2003, 6:07pm

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).

Title: Re: Cycle(L)
Post by xlh on Jun 24^th, 2003, 11:36pm

Given DFA D = (Q={q₁ ... q_n},A,q₁,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 q_i in Q, N will have states corresponding to 2 copies of Q, call them Q_i and Q_i'. Denote the j^th state in Q_i by q_ij and the j^th state in Q_i' by q_ij'. Keep all the transitions from D within each of these copies. Add epsilon transitions {(q_* -> q_ii) : q_i in Q} and {(q_ij -> q_i1') :q_j in F}. Define F' = {q_ii': q_i 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 q_k be the state of D after processing u. Then reading v would cause a transition from q_k to some state in F. On reading the string vu, N will go from q_* to q_kk by epsilon move, then reading v will lead to some state q_kj where q_j in F, then by epsilon to q_k1', then by reading u to q_kk'. So CYCLE(L(D)) is a subset of L(N)

For any word z in L(N) let q_kk' be one of the final states which is active after reading z. Since all paths from q_* to q_kk' pass through a transition q_kj -> q_k1' for some q_j 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 q_kk'. This means that D will move from q₁ to q_k while reading u and from q_k to q_j 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))

Title: Re: Cycle(L)
Post by kaltik on May 13^th, 2012, 6:21am

@ 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?