patternMinor
Definition of the cyclic shift of a formal language?
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.
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
To see the connection with the definition, consider
To answer your concrete question, $u,v \in \Sigma^*$. (The alphabet is usually denoted by $\Sigma$.)
monkey:monkey onkeym nkeymo keymon eymonk ymonkeTo 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.