2
$\begingroup$

Let be two languages $L_1,L_2$ we define the operation full-shuffle as $S(L_1,L_2)=\{w \mid w=w_1w_2...w_k\}$ such that $w_1,w_3,...\in L_1$ and $w_2,w_4...\in L_2$. In other words, the language $L$ only contains words that we can build from a word $L_1$ followed by a word from $L_2$, followed by a word from $L_1$, followed by a word from $L_2$, and so on...

How can I show that regular languages are closed by this operation ?

I have some difficulties to imagine the formalize automata resulting from this.

I did the following from p49, in Introduction to theory of computation from A. Meheshwari and M. Smid.

Let $M_1=(Q_1,\Sigma,\delta_1,q_1,F_1)$ be an NFA such that $A_1=L(M_1)$ and $M_2=(Q_2,\Sigma,\delta_2,q_2,F_2)$ be an NFA such that $A_2=L(M_2)$. We will construct an NFA $M=(Q,\Sigma,\delta,q_0,F)$ such that $L(M)=A_1A_2A_1A_2A_1...$

  1. $Q = Q_1 \cup Q_2$ ($\cup Q_1 \cup Q_2...?$ but it remains the same isn't it ?)
  2. $q_0=q_1$
  3. $F=F_1 \cap F_2$ as far as we have to have words from both $L_1$ and $L_2$.
  4. $\delta : Q\times\Sigma_\epsilon \rightarrow P(Q)$ is defined as folows :

$$\delta(r,a)=\begin{cases} \delta_1(r,a)\mbox{ if $r\in Q_1$}\\ \delta_2(r,a)\mbox{ if $r\in Q_2$}\\ \end{cases}$$

I'm new to this kind of proof and I'm not sure about it.

$\endgroup$
1
  • $\begingroup$ Rather than trying to imagine an automaton, I suggest that you try using the known closure properties of regular languages. For example, if $L_1$ and $L_2$ are regular, then so is their concatenation $L_1L_2 = \{ w_1w_2\mid w_1\in L_1, w_2\in L_2\}$. $\endgroup$
    – MJD
    Commented Jan 14, 2023 at 15:12

2 Answers 2

1
$\begingroup$

Just use regular expressions instead of automata. Indeed, $$S(L_1,L_2) = (L_1L_2)^* \cup (L_1L_2)^*L_1$$

$\endgroup$
0
0
$\begingroup$

Well, you are missing the crucial parts. First of all, the set of accepting states should be $F_1 \cup F_2$, not the intersection. The idea is that we start in $M_1$, and when we have accepted a word $w_1$ in $M_1$, then we non-deterministically choose between either stopping there, or continue reading a word $w_2$ which should be in $M_2$. Hence you must add transitions $$\delta(r,a) = \begin{cases} \delta_2(r,a) \cup \{q_1\} \text{ if } r \in F_2 \text{ and } a = \varepsilon \\ \delta_1(r,a) \cup \{q_2\} \text{ if } r \in F_1 \text{ and } a = \varepsilon\end{cases}$$ that can take you from an accept state in one of the automata to the start state in the other. This way, you can "shuffle" back and forth between $M_1$ and $M_2$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .