Register

proving a language is regular based on two regular language over same $\Sigma$ (complicated)

214 views
0 votes
0 votes
Hello,

I’ve encountered with a difficult question i don’t know how to solve. the question is about proving that a language is regular based on two language over the same $\Sigma$.

the questions goes as following:

$L_1$ and $L_2$ are regular languages over the same $\Sigma$, $(i=1,2,3,..,n)\sigma_i \in \Sigma$ $(n \geq 0)$, exists $(i = 1,2,3,…, n)\mu_1,\xi_1 \in Sigma$ for which $L^\wedge = \{\sigma_1\sigma_2...\sigma_n | \mu_1\mu_2...\mu_n \in L_2$ AND $\sigma_1\mu_1\xi_1...\sigma_n\mu_n\xi_n \in L_1$.

additional info: $\epsilon \in L^\wedge \iff \epsilon \in L_1 \land \epsilon \in L_2$ (epsilon needs to be in both to be in $L^\wedge$).

how can this thing be proven using closure properties or a multipication automaton?

i know it’s complicated and would appreciate help with it.

thank you very much your much appreciated help!
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
M_Umair_Khan42900 asked Dec 29, 2022
791 views
Show that the following pairs of regular expressions define the same language over the alphabet I = [a, b]. s(a) p(pp)*( A + p)q + q and p*q (b) A +0(0+1)* + (0+1)* 00(0+1)* and ((1*0)*01*)* (c) (s*ttt)*s* and s*(ttts*)*
Show that the following pairs of regular expressions define the same language over the alphabet I = [a, b].s(a) p(pp)*( A + p)q + q and p*q(b) A +0(0+1)* + (0+1)* 00(0+1)...
User Avatar
2 votes
2 votes
2 answers
3
Mojo-Jojo asked Sep 28, 2015
1,162 views
Why is $a^{n}b^{n} \cup a^{*}b^{*}$ regular ?
Why is $a^{n}b^{n} \cup a^{*}b^{*}$ regular ? Does this imply that a subset of non regular language can be regular ?
Why is $a^{n}b^{n} \cup a^{*}b^{*}$ regular ?Does this imply that a subset of non regular language can be regular ?
User Avatar
0 votes
0 votes
2 answers
4
Pooja Palod asked Sep 19, 2015
924 views
Consider $L_1$ and $L_2$, each over the alphabet $\Sigma$. Let $f: \Sigma \to \Sigma$ be
Consider two languages $L_1$ and $L_2$, each over the alphabet $\Sigma$. Let $f: \Sigma \to \Sigma$ ... $L_1$ is Undecidable and $L_2$ is Decidable (D) $L_1$ is Recursively Enumerable and $L_2$ is Recursive
Consider two languages $L_1$ and $L_2$, each over the alphabet $\Sigma$.Let $f: \Sigma \to \Sigma$ be a polynomial time, computable bijection, such that:$$\forall x: \le...
User Avatar
Link Copied!