3
$\begingroup$

Wikipedia says, the context-free languages are closed under

the cyclic shift of $L$ (the language $\{vu : uv \in L \}$)

So I am looking for the definition of the cyclic shift operation on formal languages.

From the quote, what are required on $u$ and $v$? Are they in $L$, or in $alphabet(L)^*$? Thanks.

$\endgroup$
  • $\begingroup$ Also called cycle or conjugation. On cs.stackexchange the closure has been discussed for regular and for context-free languages. $\endgroup$ – Hendrik Jan May 30 '14 at 6:55
5
$\begingroup$

The cyclic shift of a language $L$ consists of all cyclic shifts of the words in $L$. Instead of defining the cyclic shift formally, let me give an example. The following are all cyclic shifts of the word monkey:

monkey onkeym nkeymo keymon eymonk ymonke

To see the connection with the definition, consider nkeymo. If we write monkey as mo concatenated with nkey and then switch both parts, we get nkeymo. This corresponds to setting u=mo and v=nkey in the definition above.

To answer your concrete question, $u,v \in \Sigma^*$. (The alphabet is usually denoted by $\Sigma$.)

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.