HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to prove certain parts of one regular language restricted by another regular language is also regular?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
regularlanguagealsoproveoneanotherhowcertainrestrictedparts

Problem

I’ve encountered the following difficult question that I don’t know how to solve.

$L_1$ and $L_2$ are regular languages over the same $\Sigma$. $$\begin{align}L^\wedge=&\{σ_1σ_2...σ_n\mid n\ge1, \sigma_1, \sigma_2, \cdots, \sigma_n\in \Sigma, \\
&\exists \mu_1, \mu_2,\cdots,\mu_n,\zeta_1,\zeta_2,\cdots\, \zeta_n
\in\Sigma, \\
&\mu_1\mu_2\cdots\mu_n\in L_2,\sigma_1\mu_1\zeta_1\sigma_2\mu_2\zeta_2...\sigma_n\mu_n\zeta_n\in L_1\}\\
&\cup\{a\mid a\in L_1, a\in L_2, a=\epsilon\}\end{align}$$
where the second set on the right hand side just says that $\epsilon\in L^\wedge\Leftrightarrow \epsilon\in L_1\land \epsilon \in L_2$.

How can we prove $L^\wedge$ is regular using closure properties or a product automaton?

What i tried to do is:

Since $n \geq 0$, we can build $\Sigma^ = \{ \sigma^ | \sigma \in \Sigma \} $ $(\Sigma \cup \Sigma) \to \Sigma^*$, then for some function h we can assign $h(\sigma)=\sigma$ (also $h(\sigma')=\sigma$), so because of homomorphism $h^{-1}(L_1 \cup L_2) = \{ \sigma_1...\sigma_n |\forall 1 \leq i \leq n \to \sigma_i \in \{ \mu_i,\mu_i' \}, \mu_1...\mu_n \in L_1 \cup L_2 \} $,

So if $(L_1 \cup L_2)' = h^{-1}(L_1 \cup L_2) \cap ( \sigma'\Sigma \Sigma')*=\{ \sigma_1'\sigma_2\sigma_3'...\sigma_{n-2}'\sigma_{n-1}\sigma{n}' | \sigma_1... \sigma_n \in (L_1 \cup L_2)$ is also regular

So if for some function $f$, $f(\sigma)=\sigma$ and $f(\sigma')=\epsilon$ $(f|f:(\Sigma' \cup \Sigma) \to \Sigma^*)$

Then $f(L_1' \cup L_2') = \{ \mu_1...\mu_n | σ_1μ_1ξ_1...σ_nμ_nξ_n∈L_1 \cup L_2 = L^∧$ and if regular because of regular languages closure to homomorphism

I know it’s complicated and would appreciate help with it, seeing how to do it correctly (pretty sure I've made some mistakes along the way).

Solution

Let me point you to the proper tools.

The operation of (perfect) shuffle takes two languages $K,L\subseteq \Sigma^*$ and alternatingly takes a symbol from one of them:

$sh(K,L) = \{ a_1b_1a_2b_2 \dots a_kb_k\mid k\ge 0, a_i,b_i\in\Sigma,\text{ where } a_1a_2\dots a_k\in L\text{ and } b_1b_2\dots b_k\in K \}$

This operationhas been discused various times, using both automata and closure properties:
Proving regular languages are closed under a form of interleaving,
Show that regular languages are closed under Mix operations, and
Closure of regular languages to shuffle using closure operations, but probably more.

Then there is the kind-of reverse of this operation, given a language $K\subseteq \Sigma^*$, keep every second letter of its strings:

$2nd(K) = \{ a_2a_4 \dots a_{2k} \mid k\ge 0, a_i\in\Sigma,\text{ for some } a_1a_2\dots a_{2k}\in K \}$

An example for that is is:
If L is regular, show that even(L) is also regular. Both solutions there are enlightening.

Also in your case one needs some shuffling (to move the letters from $L_2$ within two other letters in order to compare with $L_1$) and some unshuffling (to keep every first letter of three for $L^{\land}$) but now with three letters/languages rather than two.

Context

StackExchange Computer Science Q#101843, answer score: 2

Revisions (0)

No revisions yet.