edited by
239 views
0 votes
0 votes
For the definition of the perfect shuffle operation. For languages $A$ and $B,$ let the $\text{perfect shuffle}$ of $A$ and $B$ be the language

$\text{{$w| w = a_{1}b_{1} · · · a_{k}b_{k},$ where $a_{1} · · · a_{k} ∈ A$ and $b_{1} · · · b_{k} ∈ B,$  each $a_{i}, b_{i} ∈ Σ$}}.$
 

Show that the class of context-free languages is not closed under perfect shuffle.
edited by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
2
admin asked Oct 12, 2019
227 views
Let $A = \{wtw^{R}\mid w,t\in\{0,1\}^{\ast}\:\text{and} \mid w \mid = \mid t \mid \}$. Prove that $A$ is not a CFL.
0 votes
0 votes
0 answers
4