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

16

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?

— rstern
źródło

1

Gah, to jest całkowicie problem świeżego CS, prawda? Szczerze mówiąc, nie próbowałem wiele; Miałem nadzieję, że gdzieś w literaturze istnieje ustalony algorytm i nie będę musiał wymyślać koła na nowo. Piszę tutaj oprogramowanie; Wziąłem tylko kilka kursów CS (kilka lat temu), więc w zasadzie zaczynam od Wikipedii. Wiem, że nikt nie lubi kogoś, kto nie chce pracować dla ich odpowiedzi, więc jeśli jest tu podręcznik, gazeta lub coś, na co możesz wskazać mnie zamiast wręczania mi algorytmu, to byłoby pomocne! Dzięki!

— rstern

Dodałem to jako komentarz, ponieważ jest to dość nie na temat, ale być może może ci pomóc. Konsorcjum Unicode ma kilka procesów określania podobieństwa między językami. Przeczytałem bardzo pouczający link na ich stronie, ale przez całe życie nie mogłem znaleźć dzisiaj, aby udzielić odpowiedzi. Jeśli masz czas na zbadanie tego tutaj, to ich strona FAQ unicode.org/faq

— htm11h

10

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

— Yuval Filmus
źródło

Dzięki za podpowiedź! Więc jeśli dobrze rozumiem, mogę skonstruować NFA dla niejednoznacznych słów

a następnie przetestować ten automat do pustki. Trudną częścią wydaje się być „zapewnienie, że zmiana z

na

nastąpi w dwóch różnych punktach”. Nie jestem pewien, jak to zrobić, poza pobraniem iloczynu (?) Dwóch DFA

i usunięciem wszystkich stanów produktu (

-terminal,

-terminal) - zastanawiam się, martwię się, że przejście z

NFA na

DFA zrujnowałoby pomysł

A B

$AB$

A

$A$

B

$B$

A B

$AB$

A

$A$

A

$A$

A B

$AB$

A B

$AB$

A

$A$ -terminal. Brzmi nieefektywnie; czy istnieje znany algorytm odpowiedni dla oprogramowania?

— rernern

Tak, nie brzmi to zbyt wydajnie, choć zawsze można to zrobić w inteligentny sposób. Nie znam żadnego konkretnego algorytmu dla tego problemu, ale może istnieć jeden.

— Yuval Filmus

7

Zaktualizowano (dzięki Yuval Filmus).

Biorąc pod uwagę dwa języki i z , niech $X$ $Y$ $A^*$ Twierdzę, żejest jednoznaczny wtedy i tylko wtedy, gdy językjest pusty.

\begin{aligned} X^{- 1} Y & = {u \in A^{*} ∣ there exists x \in X such that x u \in Y} \\ Y X^{- 1} & = {u \in A^{*} ∣ there exists x \in X such that u x \in Y} \end{aligned}

$\begin{align} X^{-1}Y &= \{u \in A^* \mid \text{there exists $x \in X$ such that $xu \in Y$} \} \\ YX^{-1} &= \{u \in A^* \mid \text{there exists $x \in X$ such that $ux \in Y$} \} \end{align}$

X Y

$XY$

X^{- 1} X \cap Y Y^{- 1} \cap A^{+}

$X^{-1}X \cap YY^{-1} \cap A^+$

Dowód . Załóżmy, że jest niejednoznaczny. Wtedy istnieje słowo , który ma dwa rozkładowi nad , np , w którym i . Bez utraty ogólności możemy założyć, że jest prefiksem , czyli $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 . Wynika z tego, że , skąd . Zatem . $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 . Następnie istnieją i takie, że oraz . Wynika z tego, że $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 jest niejednoznaczny. $x_2y_1 = x_1zy_1 = x_1y_2$ $XY$

Jeśli i są regularne, to zarówno i są regularne, a zatem 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}$

— J.-E. Kołek
źródło

z

$z$

Ups Aktualizuję.

— J.-E.