¿Cuándo es inequívoca la concatenación de dos idiomas regulares?

Dados los idiomas $A$ y $B$ , digamos que su concatenación $AB$ es inequívoca si para todas las palabras $w \in AB$ , hay exactamente una descomposición $w = ab$ con $a \in A$ y $b \in B$ , y de lo contrario es ambigua . (No sé si hay un término establecido para esta propiedad, ¡algo difícil de buscar!) Como ejemplo trivial, la concatenación de $\{\varepsilon, \mathrm{a}\}$ en sí misma es ambigua ( $w = \mathrm{a} = \varepsilon \mathrm{a} = \mathrm{a} \varepsilon$ ), pero la concatenación de consigo misma no es ambigua.$\{\mathrm{a}\}$

¿Existe algún algoritmo para decidir si la concatenación de dos idiomas regulares es inequívoca?

Sugerencia: dados los DFA para y B , construya un NFA que acepte palabras en A B que tengan al menos dos descomposiciones diferentes. El NFA realiza un seguimiento de dos copias del NFA estándar para A B (formado uniendo DFA para A y B con transiciones ϵ ), asegurando que el cambio de A a B ocurra en dos puntos diferentes.$A$$B$$AB$$AB$$A$$B$$\epsilon$$A$$B$

Actualizado (gracias a Yuval Filmus).

Dados dos idiomas e Y de A ∗ , dejemos X - 1$X$$Y$$A^*$ Yo afirmo queXYno es ambiguo si y solo si el lenguajeX-1X∩YY-1∩A+está vacío.

$XY$$u$$XY$$u = x_1y_2 = x_2y_1$$x_1, x_2 \in X$$y_1, y_2 \in Y$$x_1$$x_2$$x_2 = x_1z$$z \in A^+$$u = x_1y_2 = x_1zy_1$$y_2 = zy_1$. Thus $z \in X^{-1}X \cap YY^{-1}$.

Suppose now that $X^{-1}X \cap YY^{-1}$ contains some nonempty word $z$. Then there exist $x_1, x_2 \in X$ and $y_1, y_2 \in Y$ such that $x_2 = x_1z$ and $y_2 = zy_1$. It follows that $x_2y_1 = x_1zy_1 = x_1y_2$ and hence the product $XY$ is ambiguous.

If $X$ and $Y$ are regular, then both $X^{-1}X$ and $YY^{-1}$ are regular and thus $X^{-1}X \cap YY^{-1}$ is also regular (see Yuval's answer for an automaton accepting this language).