HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Definition of the cyclic shift of a formal language?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
definitionshifttheformallanguagecyclic

Problem

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.

Solution

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

Context

StackExchange Computer Science Q#26223, answer score: 5

Revisions (0)

No revisions yet.