Question

In the traditional method for cutting a deck of playing cards, the deck is arbitrarily split two parts, which are exchanged before reassembling the deck. In a more complex cut, called Scarne’s cut, the deck is broken into three parts and the middle part in placed first in the reassembly. We’ll take Scarne’s cut as the inspiration for an operation on languages. For a language $\mathbf{A}$, let $\mathbf{CUT}\mathbf{\left(}\mathbf{A}\mathbf{\right)}\mathbf{=}\mathbf{\left\{}\mathbf{yxz}\mathbf{\right|}\mathbf{xyz}\mathbf{\in }\mathbf{A}\mathbf{\}}\mathbf{.}$

a. Exhibit a language$\mathbf{B}$ for which$\mathbf{CUT}\mathbf{\left(}\mathbf{B}\mathbf{\right)}\mathbf{\ne }\mathbf{CUT}\mathbf{\left(}\mathbf{CUT}\mathbf{\left(}\mathbf{B}\mathbf{\right)}\mathbf{\right)}\mathbf{.}$

b. Show that the class of regular languages is closed under $\mathbf{CUT}$.

Short answer

a. A language B exhibit for which $\mathrm{CUT}\left(\mathrm{B}\right)\ne \mathrm{CUT}\left(\mathrm{CUT}\left(\mathrm{B}\right)\right).$

b. the class of regular languages is closed under$\mathrm{CUT}$ is proved.

Step-by-step solution

Regular language.

A language is regular if it can be expressed in terms of regular expression.A regular expression can also be described as a sequence of pattern that defines a string. Regular expressions are used to match character combinations in strings.

A language exhibit for which CUT(B)≠CUT(CUT(B)).

a).

Regular language follows deterministic finite automata which is follows the property$\mathrm{CUT}\left(\mathrm{A}\right)=\left\{\mathrm{yxz}\right|\mathrm{xyz}\in \mathrm{A}\}$. As mention in the question $\mathrm{CUT}\left(\mathrm{B}\right)\ne \mathrm{CUT}\left(\mathrm{CUT}\left(\mathrm{B}\right)\right)$that the traditional method for cutting a deck of playing cards, the deck is arbitrarily split two parts, which are exchanged before reassembling the deck. In a more complex cut, called Scarne’s cut, the deck is broken into three parts and the middle part in placed first in the reassembly. We’ll take Scarne’s cut as the inspiration for an operation on languages.

$\mathrm{yxz},\mathrm{xyz}$these string belongs to the language set $\mathrm{A}$. which (almost) saves one level of exponentiality. Moreover, we hope that this construction, though more complex, is more instructive. First handle the comparatively simple case $\mathrm{L}\left(\mathrm{A}\right)!\mathrm{L}\left({\mathrm{A}}_0\right).$ The idea of the construction is to combine A with a kind of product automaton.

Hence, Regular language follows deterministic finite automata which is follows the property $\mathrm{CUT}\left(\mathrm{A}\right)=\left\{\mathrm{yxz}\right|\mathrm{xyz}\in \mathrm{A}\}$and this will follows this property $\mathrm{CUT}\left(\mathrm{B}\right)\ne \mathrm{CUT}\left(\mathrm{CUT}\left(\mathrm{B}\right)\right)$, is proved.

The class of regular languages is closed under CUT.

b).

Let $\mathrm{A},{\mathrm{A}}_0$be deterministic finite automata. The languages denoted by cut expressions are regular, it suffices to show how to construct deterministic finite automata recognizing$\mathrm{L}\left(\mathrm{A}\right)!\mathrm{L}\left({\mathrm{A}}_0\right)\mathrm{and}\mathrm{L}\left(\mathrm{A}\right)!*$.

Here that an alternative proof would be obtained by showing how to construct alternating automata (AFAs) recognizing $\mathrm{L}\left(\mathrm{A}\right)!\mathrm{L}\left({\mathrm{A}}_0\right)\mathrm{and}\mathrm{L}\left(\mathrm{A}\right)!*$.

Such a construction would be slightly simpler, especially for the iterated cut, but since the conversion of AFAs to deterministic finite automata causes a doubly exponential size increase, prefer the construction given below, which (almost) saves one level of exponentiality. Moreover, we hope that this construction, though more complex, is more instructive. First handle the comparatively simple case $\mathrm{L}\left(\mathrm{A}\right)!\mathrm{L}\left({\mathrm{A}}_0\right).$ The idea of the construction is to combine A with a kind of product automaton of $\mathrm{A},{\mathrm{A}}_0$.

The automaton starts working like $\mathrm{A}$.At the point where $\mathrm{A}$ reaches one of its final states,${\mathrm{A}}_0$starts running in parallel with A.

However, in contrast to the ordinary product automaton, the computation of${\mathrm{A}}_0$ is reset to its initial state whenever$\mathrm{A}$ reaches one of its final states again. Finally, the string is accepted if and only if ${\mathrm{A}}_0$is in one of its final states.

By the definition of$\mathrm{L}\left(\mathrm{A}\right)!\mathrm{L}\left({\mathrm{A}}_0\right).$ and the choice of F, they imply that$\mathrm{L}\left(\mathrm{A}\right)!\mathrm{L}\left({\mathrm{A}}_0\right)\mathrm{and}\mathrm{L}\left(\mathrm{A}\right)!*$ .

Hence, the class of regular languages is closed under CUT is proved.