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)$

  • $\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$ Commented Dec 6, 2015 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.
    Commented Dec 7, 2015 at 0:10

1 Answer 1


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.

  • $\begingroup$ למה אם אחליף את כל האלפבית זה יבטיח שקיימות 2 מילים שונות? $\endgroup$
    – 3SAT
    Commented Dec 6, 2015 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
    Commented Dec 6, 2015 at 21:35

Your Answer

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

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