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

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

• 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. Dec 6 '15 at 21:02
• 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.
– D.W.
Dec 7 '15 at 0:10

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'$.