2
$\begingroup$

I'm self studying Introduction to Theory of computation and I'm a bit confused about a problem definition. I'm trying to understand and verify whether my proof is correct or not.

Question: Prove that the regular language is closed under perfect shuffle

The perfect shuffle between two languages $A$ and $B$ is defined as:

$$\{w | w = a_ib_i\cdots a_kb_k\}, \text{ where } a_1\cdots a_k \in A \text{ and } b_1\cdots b_k \in B \text{ and each } a_i, b_i \in \Sigma\}$$

Proof:

If $A = (Q_A, \Sigma_A, \delta_A, l_0, F_A)$ and $B = (Q_B, \Sigma_B, \delta_B, m_0, F_B)$

Let $M = (Q, \Sigma, \delta, q, F )$ be the machine recognizing the closure of the language.

where,

  1. $$Q = Q_A \cup Q_B$$

  2. $$\Sigma = \Sigma_A \cup \Sigma_B$$

  3. $$q = l_0$$

  4. $$F = F_B$$

  5. And

    $$ \delta = \begin{cases} \delta_1(q_i, r), & \forall r \in A \\ \delta_2(q_i, r), & \forall r \in B \end{cases}$$

    where, $\delta_1(q_i, r) = l_i, \text{ where } l_i \in B$ and $\delta_2(q_i, r) = m_{i+1}, \text{ where } m_{i} \in A$.

The confusion about the correctness of proof primarily stems from $F = F_B$ is this something that is true in my DFA of perfect shuffle?

$\endgroup$

1 Answer 1

3
$\begingroup$

This does not work, I am afraid. Your state space is the union $Q_A\cup Q_B$ of the individual spaces, it should be the direct product $Q_A\times Q_B$ instead. See for example this answer: Zigzag concatenation of two languages. The reason is that one should also remember the state of the other automaton when switching between the two.

$\endgroup$
6
  • $\begingroup$ But why do we need to remember the state when all we have to do is alternate between the machines, especially since in our case $a_i, b_i \in \Sigma$? Is something like this not possible: imgur.com/Gxw1H8z.png $\endgroup$ Sep 18, 2022 at 17:56
  • $\begingroup$ Yes, that zig-zag is what you are effectively doing, but the next state $l_2$ after $m_1$ is determined by $l_1$ so we should definitely remember that state. The combined "zipped" automaton recalls two states (one from each of the two automata) and also who's turn it is. $\endgroup$ Sep 18, 2022 at 18:07
  • $\begingroup$ I'm afraid I don't understand why $l_2$ has to depend on $l_1$, when creating the new transition function doesn't the subscript "encode" this information already. Am I wrong to assume subscript encodes such information? Also if I were to write transition function for this wouldn't it be something like what I wrote in the question. $\endgroup$ Sep 18, 2022 at 18:24
  • $\begingroup$ Like if we can do $\delta(q_i, a) = q_{i+1}$ what is stopping us from $\delta(m_i, b) = l_{i+1}$? $\endgroup$ Sep 18, 2022 at 18:26
  • $\begingroup$ Upon writing and thinking to myself. I am dumb to think that we can find $l_{i+1}$ without the transition function for language $A$. To say it in more obvious way, $l_{i+1}$ is next to $l_i$ only because of the transition function's existence and we can't get there if we don't have an $l_i$. This will take me a minute more to get it fully. But I think I understand it better now. Thanks a lot! $\endgroup$ Sep 18, 2022 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.