TIFR CSE 2024 | Part B | Question: 5

Question

For two languages $\text{A, B}$ over the alphabet $\Sigma$, let the perfect shuffle of $\text{A}$ and $\text{B}$ be the language

\begin{Bmatrix}
w=a_1 b_1 a_2 b_2 \cdots a_k b_k \text{where} a_1 a_2 \cdots a_k \in \text{A} and b_1 b_2 \cdots b_k \in B.& \\ \text{and} k \in\mathbb{N}
 & 
\end{Bmatrix}

Consider the following statements.

1. If $\text{A}$ and $\text{B}$ are regular, then perfect shuffle of $\text{A}$ and $\text{B}$ is regular.
2. If $\text{A}$ and $\text{B}$ are regular, then perfect shuffle of $\text{A}$ and $\text{B}$ is context-free.
3. If $\text{A}$ and $\text{B}$ are decidable, then perfect shuffle of $\text{A}$ and $\text{B}$ is decidable.

Which of above statements is/are true?

• A. All of $\text{(i), (ii) and (iii)}$.
• B. Only $\text{(i) and (ii)}$.
• C. Only $\text{(ii)}$.
• D. Only $\text{(ii) and (iii)}$.
• E. None of $\text{(i), (ii), (iii)}$ is true.

   

Answer 1

For 1 and 2 proofs are in pdfs

http://www.cs.nthu.edu.tw/~wkhon/assignments/assign1ans.pdf

http://im.ntu.edu.tw/~tsay/dokuwiki/lib/exe/fetch.php?media=courses:theory2014:theory2014mid_s.pdf