Kiedy połączenie dwóch regularnych języków jest jednoznaczne?

Biorąc pod uwagę języki i , powiedzmy, że ich konkatenacja jest jednoznaczna, jeśli dla wszystkich słów istnieje dokładnie jeden rozkład z i , a niejednoznaczny inaczej. (Nie wiem, czy istnieje ustalony termin dla tej właściwości - trudna rzecz do wyszukania!) Jako trywialny przykład konkatenacja z samym sobą jest niejednoznaczna ( ), ale konkatenacja z samym sobą jest jednoznaczna.$A$$B$$AB$$w \in AB$$w = ab$$a \in A$$b \in B$$\{\varepsilon, \mathrm{a}\}$$w = \mathrm{a} = \varepsilon \mathrm{a} = \mathrm{a} \varepsilon$$\{\mathrm{a}\}$

Czy istnieje algorytm decydujący o tym, czy połączenie dwóch regularnych języków jest jednoznaczne?

UWAGA: względu DFAS dla i B , skonstruować NFA która przyjmuje słowa A B o co najmniej dwie różne rozkładowi. NFA śledzi dwie kopie standardowego NFA dla A B (utworzone przez połączenie DFA dla A i B z przejściami ϵ ), zapewniając, że przejście z A do B nastąpi w dwóch różnych punktach.$A$$B$$AB$$AB$$A$$B$$\epsilon$$A$$B$

Zaktualizowano (dzięki Yuval Filmus).

Biorąc pod uwagę dwa języki i Y z A ∗ , niech X - 1$X$$Y$$A^*$ Twierdzę, żeXYjest jednoznaczny wtedy i tylko wtedy, gdy językX-1X∩YY-1∩A+jest pusty.

Dowód . Załóżmy, że jest niejednoznaczny. Wtedy istnieje słowo u , który ma dwa rozkładowi nad X Y , np U = x 1 r 2 = x 2 y 1 , w którym x 1 , x 2 ∈ X i Y 1 , Y 2 ∈ Y . Bez utraty ogólności możemy założyć, że x 1 jest prefiksem x 2 , czyli 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$ dla niektórych z ∈ A + . Wynika z tego, że u = x 1 y 2 = x 1 z y 1 , skąd y 2 = z y 1 . Zatem z ∈ X - 1 X ∩ Y Y - 1 .$x_2 = x_1z$$z \in A^+$$u = x_1y_2 = x_1zy_1$$y_2 = zy_1$$z \in X^{-1}X \cap YY^{-1}$

Załóżmy teraz, że zawiera jakieś niepuste słowo z . Następnie istnieją x 1 , x 2 ∈ X i y 1 , y 2 ∈ Y takie, że x 2 = x 1 z oraz y 2 = z y 1 . Wynika z tego, że x 2 y 1 = x 1 z y 1$X^{-1}X \cap YY^{-1}$$z$$x_1, x_2 \in X$$y_1, y_2 \in Y$$x_2 = x_1z$$y_2 = zy_1$ a zatem iloczyn X Y jest niejednoznaczny.$x_2y_1 = x_1zy_1 = x_1y_2$$XY$

Jeśli i Y są regularne, to zarówno X - 1 X, jak i Y Y - 1 są regularne, a zatem X - 1 X ∩ Y Y - 1 jest również regularne (patrz odpowiedź Yuvala dla automatu akceptującego ten język).$X$$Y$$X^{-1}X$$YY^{-1}$$X^{-1}X \cap YY^{-1}$