Question

Let the rotational closure of language A be.

$\mathbf{RC}\mathbf{\left(}\mathbf{A}\mathbf{\right)}\mathbf{=}\mathbf{\left\{}\mathbf{yx}\mathbf{\right|}\mathbf{xy}\mathbf{\in }\mathbf{A}\mathbf{\}}$

a. Show that for any language A, we have $\mathbf{RC}\mathbf{\left(}\mathbf{A}\mathbf{\right)}\mathbf{=}\mathbf{RC}\mathbf{\left(}\mathbf{RC}\mathbf{\left(}\mathbf{A}\mathbf{\right)}\mathbf{\right)}\mathbf{.}$

b. Show that the class of regular languages is closed under rotational closure.

Short answer

a)For any language$\mathrm{A}$$,\mathrm{RC}\left(\mathrm{A}\right)=\mathrm{RC}\left(\mathrm{RC}\left(\mathrm{A}\right)\right)$ is proved.

b)The rotational closure of language$\mathrm{A}$ to be $\mathrm{RC}\left(\mathrm{A}\right)=\left\{\mathrm{yx}\right|\mathrm{xy}\in \mathrm{A}\}$is closed under rotational closure.

Step-by-step solution

Step 1: Rotational closure.

The cyclic shift also called rotation or conjugation and a language is defined as $\left\{\mathrm{yx}\right|\mathrm{xy}\in \mathrm{A}\}$. The context-free languages are closed under this operation. The rotation closure, conjugation, and cyclic shift contains a language which rotates and seems same which is belongs to $\mathrm{A}$.

Step 2: Rotational closure of language.

a).

$\mathrm{RC}\left(\mathrm{A}\right)=\mathrm{RC}\left(\mathrm{RC}\left(\mathrm{A}\right)\right)$

To decide non deterministically at the beginning the word is cycled, and have a copy of the automaton for every case. In terms of the automaton, that means that in which state$\mathrm{D}$ would have been after consuming a word's prefix (which is a suffix of our input), and start in that state.

Now the construction for every state, separate$\mathrm{D}$ into two parts ${\mathrm{A}}_2$ contains the states from which $\mathrm{q}$ is reachable and ${\mathrm{A}}_2$the states that are reachable from $\mathrm{q}$.

We get $\left|\mathrm{Q}\right|$ automata of this form; create a new initial state which has $\mathrm{\epsilon }$ transitions to all their starting states. The resulting automaton accepts$\mathrm{cycle}\left(\mathrm{L}\right)$ Altogether, here, most $\left|\mathrm{Q}\right|=\left(2\right|\mathrm{Q}|+1)+1$states, only$\left|\mathrm{Q}\right|$ more states than the reference claims are possible.

Here the achieved state is act as$\left|\mathrm{Q}\right|=\left(2\right|\mathrm{Q}|+1)+1$ states by modifying the component automata a little bit; eliminate all q0q0 by replacing the incoming $\mathrm{\epsilon }$-transitions with copies of its outgoing transitions. That is, for every pair of transitions $({\mathrm{q}}_1,\mathrm{\epsilon },{\mathrm{q}}_0),({\mathrm{q}}_0,\mathrm{a},{\mathrm{q}}_2)$introduces a transition $({\mathrm{q}}_1,\mathrm{a},{\mathrm{q}}_2)$.Hence$\mathrm{RC}\left(\mathrm{A}\right)=\mathrm{RC}\left(\mathrm{RC}\left(\mathrm{A}\right)\right)$ is proved.

Proving the class of regular language is closed under rotational closure.b).

By using deterministic finite automata, a finite automata for the original language, construct one for the cyclic shift. The new automaton operates in two stages, corresponding to the $\mathrm{y}$ and the $\mathrm{x}$part of the word $\mathrm{yx}$where $\mathrm{yx}$is in the original language.

In the first stage, whenever the automaton would like to pop a non-terminal $\mathrm{A}$it can instead push a non-terminal $\mathrm{A}\text{'}$, the idea is that at the end of the first stage, the stack would contain, in reverse order, the symbols that are found in the stack after reading $\mathrm{x}$by the original automaton. In the second stage (the switch is non-deterministic), instead of pushing a non-terminal $\mathrm{AA}$, are allowed to pop a non-terminal $\mathrm{A}\text{'}$.

If the original automaton can indeed generate the stack upon reading$\mathrm{x}$, then the new one would be able to exactly pop the entire stack.

Here suppose we are given a deterministic finite automaton with alphabet $\sum$, set of states, set of accepting states, non-terminals, initial state, and a set of allowable transitions. Each allowable transition is of the form$(\mathrm{q},\mathrm{a},\mathrm{A},\mathrm{q}\text{'},\mathrm{\alpha })$ meaning that when in state, upon and the new deterministic finite automata has a new non-terminal $\mathrm{A}\text{'}$for each.

Hence, the rotational closure of language A to be$\mathrm{RC}\left(\mathrm{A}\right)=\left\{\mathrm{yx}\right|\mathrm{xy}\in \mathrm{A}\}$is closed under rotational closure for regular language.