Quand la concaténation de deux langues régulières est-elle sans ambiguïté?

Étant donné les langues $A$ et $B$ , disons que leur concaténation $AB$ est sans ambiguïté si pour tous les mots $w \in AB$ , il y a exactement une décomposition $w = ab$ avec $a \in A$ et $b \in B$ , et ambiguë sinon. (Je ne sais pas s'il existe un terme établi pour cette propriété - chose difficile à rechercher!) Comme exemple trivial, la concaténation de $\{\varepsilon, \mathrm{a}\}$ avec elle-même est ambiguë ( ), mais la concaténation de { a } avec elle-même est sans ambiguïté.$w = \mathrm{a} = \varepsilon \mathrm{a} = \mathrm{a} \varepsilon$$\{\mathrm{a}\}$

Existe-t-il un algorithme pour décider si la concaténation de deux langues régulières est sans ambiguïté?

Astuce: étant donné les DFA pour et B , construisez un NFA qui accepte les mots dans A B ayant au moins deux décompositions différentes. Le NFA conserve une trace de deux copies du NFA standard pour A B (formé en joignant les DFA pour A et B avec ϵ transitions), garantissant que le passage de A à B se produit à deux points différents.$A$$B$$AB$$AB$$A$$B$$\epsilon$$A$$B$

Mise à jour (merci à Yuval Filmus).

Étant donné deux langues et Y de A ∗ , soit X - 1$X$$Y$$A^*$ Je prétends queXYest sans ambiguïté si et seulement si la langueX-1X∩YY-1∩A+est vide.

Preuve . Supposons que soit ambigu. Ensuite , il existe un mot u qui a deux décompositions sur X Y , par exemple u = x 1 y 2 = x 2 y 1 , où x 1 , x 2 ∈ X et y 1 , y 2 ∈ Y . Sans perte de généralité, nous pouvons supposer que x 1 est un préfixe de x 2 , c'est-à-dire x 2 = $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$ for some $z \in A^+$. It follows that $u = x_1y_2 = x_1zy_1$, whence $y_2 = zy_1$. Thus $z \in X^{-1}X \cap YY^{-1}$.

$X^{-1}X \cap YY^{-1}$$z$$x_1, x_2 \in X$$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).