1
$\begingroup$

How can we show that the class of regular languages is closed under the following operation?

Let $L_1$ and $L_2$ be laguages over $\Sigma=\{0, 1\}$.

The operation is: $$\{x \in L_1 \mid \text{ for some } y \in L_2, \text{ strings } x \text{ and } y \text{ contains equal numbers of } 1s \}$$

Is the only way to show this to create a NFA of the new language?

I have done the following:

Let $M_{L_1}=(Q_{L_1},\Sigma ,\delta_{L_1},q_{L_1},F_{L_1})$ the DFA that recognizes $L_1$ and $M_{L_2}=(Q_{L_2},\Sigma ,\delta_{L_2},q_{L_2},F_{L_2})$ the DFA that recognizes $L_2$.

Let $M=(Q,\Sigma ,\delta,q,F)$ the NFA that recognizes the operation.

$Q=Q_{L_1}\times Q_{L_2}, \ \ q=(q_{L_1},q_{L_2})$.

Is this correct? Which is the transition function?

Improve this question
$\endgroup$
1
  • $\begingroup$ How can we say if your approach has merit when you leave out the single most important piece? And no, giving an NFA is not the only way; see our reference question. $\endgroup$
    – Raphael ♦
    Mar 2, 2015 at 11:44

2 Answers 2

Reset to default
4
$\begingroup$

Let $$ L = \{ x \in L_1 \mid \text{there exists }y \in L_2 \text{ such that } |x|_1 = |y|_1\} $$ Let $\pi: \Sigma^* \to a^*$ be the homomorphism defined by $\pi(u) = a^{|u|_1}$. I claim that $$ L = L_1 \cap \pi^{-1}(\pi(L_2)) $$ Since regular languages are closed under homomorphisms, inverses of homomorphisms and intersection, it will follow that $L$ is regular.

Proof of the claim. \begin{align} L_1 \cap \pi^{-1}(\pi(L_2)) &= \{ x \in L_1 \mid \pi(x) \in \pi(L_2) \} \\ &= \{ x \in L_1 \mid \text{there exists }y \in L_2 \text{ such that } \pi(x) = \pi(y)\}\\ &= \{ x \in L_1 \mid \text{there exists }y \in L_2 \text{ such that } |x|_1 = |y|_1\} \\ &= L \end{align}

Improve this answer
$\endgroup$
1
  • $\begingroup$ - - - very nice - - - $\endgroup$
    – babou
    Mar 2, 2015 at 23:11
3
$\begingroup$

Well, you are almost correct so far. But the trick is in the transitions. Cross-product construction, as you suggest, means that you intend to mimic both NFAs. But in this case you do not mimic them exactly in the same way. The part corresponding to the automaton $M_1$ for $L_1$ is mimicked for acceptance of the input string, while the part corresponding to the automaton $M_2$ for $L_2$ ignores the input and mimicks non-deterministically acceptance of some arbitrarily chosen input (ignoring the real input).

Furthermore, the states are not just $(q_{L_1},q_{L_2})$, but there is a third component, which is true or false, so that states are of the form $(q_{L_1},q_{L_2}, eq)$, where $eq$ can be $true$ or $false$.

This third component is true when you have mimicked scanning the same number of $1$'s for $M_1$ and for $M_2$.

But remember that the first is scanning the input string, while the second is scanning a non-existent randomly chosen string.

The last point is that you mimick both NFA asynchronously. Either you mimick the first or you mimick the second. Never both at the same time.

So you start mimicking the first on the true input until you scan a 1. Then you start mimicking the second on its non-deterministically chosen input until you scan a 1. Then you resume with the first until you scan a 1. Then you resume the second until ... etc. And you are careful that the $eq$ component of the state triple is $true$ only when both computations have seen the same number of $1$'s. You stop also when computations reach the end of their input (except for empty transitions), whether real input or made-up input.

Accepting states are triple of the form $(q_{a1},q_{a2}, true)$ where $q_{a1}$ and $q_{a2}$ are accepting states of the two initial automata.

Good luck

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ You can avoid the third component by synchronizing the simulation of the two automata on the $1$-transitions. The $0$-transitions are "independent". $\endgroup$
    – Hendrik Jan
    Mar 2, 2015 at 9:23
  • 1
    $\begingroup$ @HendrikJan Yes. That is a result of designing while writing. Actually, I should have said that the two simulations are synchronized on reading $1$. They have to read 1 simultaneaously. That should give a way of replacing 1 by äny substring. $\endgroup$
    – babou
    Mar 2, 2015 at 9:56
  • $\begingroup$ Could you explain to me further the way to avoid the third component?? $\endgroup$
    – Mary Star
    Mar 2, 2015 at 23:00
  • $\begingroup$ @MaryStar Thinking more about it, I am not sure you can avoid this third component. It also has a role telling you whether you are mimicking the first or the second automaton. $\endgroup$
    – babou
    Mar 2, 2015 at 23:09
  • $\begingroup$ I found in my book the following description of $M$: $$ - Q=Q_{L_1} \times Q_{L_2}$$ $$- \text{ for each } (q, r) \in Q \text{ and } \Sigma, \delta \text{ is defined as followed } \\ \delta \left (\left (q, r\right ), a\right )=\left\{\begin{matrix} \{(\delta_{L_1}(q,0),r)\} & \text{ if } a=0\\ \{(\delta_{L_1}(q,1),\delta_{L_2}(r,1))\} & \text{ if } a=1\\ \{(q,\delta_{L_2}(r,0))\} & \text{ if } a=\varepsilon \end{matrix}\right.$$ $$- q_0=(q_{L_1}, q_{L_2})$$ $$ - F=F_{L_1} \times F_{L_2}$$ Could you explain to me the transition function $\delta$ ?? @babou $\endgroup$
    – Mary Star
    Mar 9, 2015 at 23:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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