2
$\begingroup$

I am having hard time proving that the following language,comprised from two regular languages $L_1,L_2$(over the same $\Sigma$)is indeed regular:

$$L^\frown = \{ w\in \Sigma^* | w=u\sigma_1\mu_1...\sigma_n\mu_nv\}$$

  • $u,v \in \Sigma^*$

  • $0\leq n$, for every i($1\leq i \leq n$): $\sigma_i,\mu_i \in \Sigma$

  • $\sigma_1...\sigma_n \in L_1$

  • $\mu_1...\mu_n \in L_2$

I don't understand how to prove if because of the suffix and prefix(u,v accordingly).

If it weren't for u,v what I think I would've done is building an automaton(Deterministic finite automaton): $A=\left(Σ,Q1xQ2x\left\{1,2\right\},\left(q01,q02,2\right),F1xF2x2,δ\right)$, Ending in accepting iff both automatons that accept each language end in an accepting state, and $L_2$ needs to be after $L_1$ from the language's description. However, I don't know how to deal with the u,v in the beginning and in the end. I am not sure how to configure it correctly to prove $L^\frown$ is regular.

Would very much appreciate your assistance with it.

Improve this question
$\endgroup$
1
  • $\begingroup$ I must be missing something. Isn't $L⌢$ just $Σ∗$? Set $u = w$ and $n =0$. $\endgroup$ Commented Oct 23, 2019 at 7:39

1 Answer 1

Reset to default
2
$\begingroup$

Your language is the concatenation $\Sigma^* L \Sigma^*$, where $L$ is the so-called perfect shuffle of $L_1$ and $L_2$. There are at least two proofs that the perfect shuffle of two regular languages is regular on this site: using automata and using closure operations.

If you are hell-bent on constructing an automaton for $\Sigma^* L \Sigma^*$, start with one for $L$, then follow the automata proof of closure under concatenation (which constructs an NFA).

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.