Question

For string W and t , write if the symbols of W are a permutation of the symbols of t . In other word,$\mathit{w}\mathbf{\doteq }\mathit{t}$ if t and W have the same symbols in the same quantities, but possibly in a different order.

For any string W , defines $\mathit{S}\mathit{C}\mathit{R}\mathit{A}\mathit{M}\mathit{B}\mathit{L}\mathit{E}\mathbf{\left(}\mathbf{w}\mathbf{\right)}\mathbf{=}\mathbf{\left\{}\mathbf{t}\mathbf{|}\mathbf{t}\mathbf{\doteq }\mathbf{w}\mathbf{\right\}}$. For any language A, let .$\mathit{S}\mathit{C}\mathit{R}\mathit{A}\mathit{M}\mathit{B}\mathit{L}\mathit{E}\mathbf{\left(}\mathbf{A}\mathbf{\right)}\mathbf{=}\mathbf{\left\{}\mathbf{t}\mathbf{|}\mathbf{t}\mathbf{\in }\mathbf{S}\mathbf{C}\mathbf{R}\mathbf{A}\mathbf{M}\mathbf{B}\mathbf{L}\mathbf{E}\mathbf{\left(}\mathbf{w}\mathbf{\right)}\mathbf{\text{\hspace{0.17em}for\hspace{0.17em}some\hspace{0.17em}}}\mathbf{w}\mathbf{\in }\mathbf{A}\mathbf{\right\}}$

1. Show that if$\mathbf{\sum }\mathbf{=}\mathbf{\{}\mathbf{0}\mathbf{,}\mathbf{1}\mathbf{\}}$ , then the $\mathit{S}\mathit{C}\mathit{R}\mathit{A}\mathit{M}\mathit{B}\mathit{L}\mathit{E}$of a regular language is context free.
2. What happens in part (a) if$\sum$ contains three or more symbols? Prove your answer.

Short answer

1. The $SCRAMBLE$of a regular language is context-free.
2. The $SCRAMBLE$of a regular language with three or more symbols is not a context free.

Step-by-step solution

Explain Context-free Language

Context-free grammar generates context-free languages. The context-free languages are the set of identical languages that can be recognized by the pushdown automata.

Step 2:Show that if ∑={0,1}, then theSCRAMBLE of a regular language is context free

a.

Consider the language $B=\left(10\right)*$over the input $\sum =\{0,1\}$, the $SCRAMBLE$have all the permutations of the string. The Finite Automata of the language accepts the $SCRAMBLE$of the language.

Use the pushdown automata to$SCRAMBLE\left(L\right)$ of a regular language is context free. Consider the input , $w=w_1{w}_2{w}_3\dots w_n$to the pushdown automata the nondeterministically works to find the permutation of the string in the regular language. If the pushdown automata guesses that $w_i=u_i$, then the transition occurs by reading the input. If the pushdown automata guesses that $w_i\ne u_i$, then the transition will be null.

The acceptance condition for the pushdown automata is that if is a permutation for string $u$, then there must be a path that lead to the accept state with empty state.

Therefore, the$SCRAMBLE$of the given regular language is a context-free.

Step 3:What happens in part (a) if  ∑contains three or more symbols? Prove your answer. 

b.

Consider the input $\sum =\{0,1,2\}$, the language $L=\left(210\right)*$. If the intersection of $SCRAMBLE\left(L\right)$is regular, then the language is regular. Consider the language $M=2*1*0*$and apply the intersection of $SCRAMBLE\left(L\right)$,which is not a CFL.

The pushdown automata that takes three or more inputs cannot be drawn.

Therefore, The $SCRAMBLE$of a regular language with three or more symbols is not a context free.