4
$\begingroup$

So glad to find this place. I have been struggling for quite a while with this given question and i am not sure how to fully address it.

The question: $L_1$ and $L_2$ are regular languages over the same $\Sigma$. prove that the following language is regular as well:

$L^\frown \:=\left\{\:w\:\in L_1 | \:w=\sigma _1\mu _1\xi _1\sigma \:_2\mu \:_2\xi \:_2...\sigma \:_n\mu \:_n\xi \:_n\right\}$ Where $n \geq 0$, for every i:$\left(1\:\le i\:\le n:\:\sigma _i\mu _i\xi _i\:\in \Sigma \right)$, $\mu_1\mu_2...\mu_n \in L_2$.

Prove using: 1)Closure properties. 2)Building an multipication automaton

My try:

1)I do not understand how to define the homomorphism from which I can deduct using closure properties that the given language is indeed regular.

2)Since both $L_1$ and $L_2$ are regular, There exist two deterministic finite automatas that can accept them: $A^i\:=\:\left(\Sigma ,\:Q^i,q_0^i,F^i,\delta ^i\right)$ ($i\:\in \left\{\:1,2\right\})$. So, let L be the automaton that accepts those two languages: let L be $L\:=\:\left(\Sigma \:,\:Q^1\:X\:Q^2,\left(q_0^1,q_0^2\right),F^1X\:F^2,\delta \:\right)$. However, here I don't know what its transition function should be

Would really appreciate your help with it, if possible with explanations to understand so I'll be able to overcome similar questions in the future.

Thank you so much!

$\endgroup$
  • $\begingroup$ Your question sounds familiar. It might have been asked before. $\endgroup$ – Yuval Filmus Jun 10 at 7:56
  • $\begingroup$ I've only encountered one similar question, but it is different and i cannot deduct how to solve this using that question. in addition, it will be most profitable for me and i believe for others if people will address this question and no other, including my remarks, so it will be easier to learn $\endgroup$ – Auto Jun 10 at 8:06
  • $\begingroup$ @YuvalFilmus - could you please help me withhttps://cs.stackexchange.com/questions/111232/using-pumping-lemma-to-show-a-language-is-not-context-freecomplicated ? been struggling for it for more than a week, tried to prove it a lot of times, but i just don't understand it. would really appreciate learning from the answer to understand how to approach complicated languages like that. i really tried by myself but failed $\endgroup$ – Auto Jun 28 at 7:14
1
$\begingroup$

Proof using closure properties

Let $add\colon \Sigma \to \Sigma^*$ be a regular substitution that maps $\mu \in \Sigma$ to $\{ \sigma \mu \xi : \sigma, \xi \in \Sigma \}$ (the image is regular since it is finite). Then your language is $L_1 \cap add(L_2)$.

Proof using product automaton

Let $(\Sigma, Q^i, q_0^i, F^i, \delta^i)$ be automata accepting $L_i$ (for $i = 1,2$). We construct a new automaton $(\Sigma, Q, q_0, F, \delta)$ where:

  • $Q = Q^1 \times Q^2 \times \{1,2,3\}$.
  • $q_0 = (q_0^1,q_0^2,1)$.
  • $F = F_1 \times F_2 \times \{1\}$.
  • $\delta((q^1,q^2,1),\sigma) = (\delta^1(q^1,\sigma),q^2,2)$.
  • $\delta((q^1,q^2,2),\sigma) = (\delta^1(q^1,\sigma),\delta^2(q^2,\sigma),3)$.
  • $\delta((q^1,q^2,3),\sigma) = (\delta^1(q^1,\sigma),q^2,1)$.

The product automaton keeps track of the state in both automata, as well as the location within the triple $\sigma_i \mu_i \xi_i$ (this is the purpose of the third argument).

$\endgroup$
  • $\begingroup$ Thank you very much! studying your answer $\endgroup$ – Auto Jun 10 at 10:14
  • $\begingroup$ could you elaborate more on using closure properties? not fully getting it yet. would really appreciate additional explanation. after the substitution shouldn't there be an homomorphism? $\endgroup$ – Auto Jun 10 at 10:56
  • $\begingroup$ Why should there be a homomorphism following a substitution? $\endgroup$ – Yuval Filmus Jun 10 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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