0
$\begingroup$

Let $A_1=(Q,\Sigma,q_0,F_1,\delta _1)$ and $A_2=(P,\Sigma ,p_0,F_2,\delta _2)$ a finite non determinustic automaons.

Describe algorithm that deside if there are two words $x$ and $y$ in the same length such that $x\in L(A_1)$ and $y\in L(A_2)$

Hint: Intersection automaton

My try

To bulid the intersection automaton $L_1\cap L_2$ and check if $L_1\cap L_2 \neq \varnothing$ with $"\color{blue}{\text{emptiness problem algorithm} }"$ and if $L_1\cap L_2 \neq \varnothing$ so $\exists $ word $w$ such that $w \in \mathscr L(L_1\cap L_2)$

$\endgroup$
  • $\begingroup$ On the right direction, but this will decide on a single word $w$ in both languages, whereas here one allows two different words $x,y$ in the respective languages that are of the same length. $\endgroup$ – Hendrik Jan Dec 6 '15 at 21:02
  • $\begingroup$ Also posted on Math.SE. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, feel free to flag for migration. $\endgroup$ – D.W. Dec 7 '15 at 0:10
2
$\begingroup$

Consider the NFA $A_1=(Q,\Sigma,q_0,F_1,\delta_1)$. Observe that an accepting run of $A_1$ induces an accepted word. That is, we don't really care about the alphabet of the automaton if we only want to consider word length.

Thus, instead of constructing the intersection automaton directly, first change the alphabet of both automata to be $\Sigma=\{a\}$, by changing the letters in all the transitions to $a$. That is, for a transition $\delta_1(q,\sigma)=q'$, change the transition to $\delta(q,a)=q'$.

Now construct the product automaton, and check emptiness.

I'm leaving the correctness proof as an exercise.

$\endgroup$
  • $\begingroup$ למה אם אחליף את כל האלפבית זה יבטיח שקיימות 2 מילים שונות? $\endgroup$ – 3SAT Dec 6 '15 at 21:25
  • 1
    $\begingroup$ Translating @Nehorai 's comment: Why would changing the alphabet guarantee two different words? Answer: There is no requirement for the words to be different. However, they are not required to be the same word, which is why the intersection automaton is not enough by itself, and we need to ignore the alphabet. $\endgroup$ – Shaull Dec 6 '15 at 21:35

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.