Rozpoznawanie automatów

Pozwolić $\Sigma$ być skończonym alfabetem. kod $X$ nad $\Sigma$ jest podzbiorem $\Sigma^*$ tak, że każde słowo w $X^*$ może być jednoznacznie przedstawiony jako połączenie słów w $X$ . Kod $X$ jest skończony, jeśli $|X|$ jest skończony. Co wiadomo na temat (minimalnego) rozpoznawania automatów $X^*$ dla skończonego kodu ? Czy istnieje jakaś charakterystyka takich automatów (pod względem budowy automatu, bez znajomości )? Czy to możliwe, mając taki automat, wyodrębnić kod w czasie wielomianowym? $X$ $X$ $X$

Interesują mnie również te pytania, gdy pomijamy fakt, że jest kodem, tzn. Zakładamy, że jest skończonym zestawem słów. $X$ $X$

automata-theory Andrew Ryzhikov
źródło

Co chcesz wiedzieć o takich automatach? Wydaje się, że łatwo jest zbudować DFA

X^{*}

$X^*$ którego rozmiar można łatwo scharakteryzować (jest to w zasadzie liczba unikalnych prefiksów ciągów w

X

$X$ , a zatem jest co najwyżej sumą długości słów w

X

$X$ ; w szczególności jest to wielkość wielomianowa). Biorąc pod uwagę taki DFA, wydaje się, że łatwo jest też wyodrębnić słowa kodowe

X

$X$ poprzez wyliczenie wszystkich cykli z węzła początkowego z powrotem do siebie. Jakie konkretnie są twoje pytania? Jakie myślenie już zrobiłeś? Zobacz część naszego Centrum pomocy „Pytania powinny opierać się na ...” .

@DW oczywiście nie wszystkie automaty mają tę właściwość. Pytam więc, czy istnieje (mam nadzieję, wielomian) charakterystyka takich automatów. Nie wiem też, jak wyodrębnić

X

$X$ wyliczając wszystkie cykle od stanu początkowego do siebie. W rzeczywistości może istnieć nieskończona liczba cykli, ponieważ nie możemy ograniczać się tylko do cykli bez samo-skrzyżowań. Czy możesz być bardziej szczegółowy?

Andrew Ryzhikov,

Jeśli dobrze rozumiem, zapytałeś o minimalne automaty. Myślę, że wszystkie minimalne DFA będą izomorficzne do tego, który opisałem. Jeśli pytasz o wszystkie automaty, niekoniecznie minimalne, proponuję edytować pytanie w celu wyjaśnienia. Nie rozumiem, dlaczego nie można ograniczać się tylko do cykli bez skrzyżowań; właściwość bez prefiksu oznacza, że można to bezpiecznie zrobić, a jeśli

X

$X$ jest skończony, będzie tylko tyle takich cykli. Sugeruję, abyś przemyślał problem przez chwilę, a następnie edytuj pytanie, aby udostępnić wszystkie wyniki, które udało ci się do tej pory wymyślić.

Czy to pytanie nie jest takie samo jak pierwsza wersja cstheory.stackexchange.com/questions/4284/… , gdzie

K

$K$ i

K^{'}

$K'$ może się różnić, poza tym, że pytasz również o czas działania?

domotorp

@domotorp Masz rację, sprawdzanie, czy zestaw słów jest kodem, można wykonać w czasie wielomianowym i jest to dość dobrze znany fakt (patrz np. www-igm.univ-mlv.fr/~berstel/LivreCodes/ Codes.html , podsekcja 0.4). Chcę, aby tylko minimalny automat rozpoznający coś sprawdził, czy to coś jest gwiazdą kodu.

Andrew Ryzhikov

Odpowiedzi:

Ponieważ przez długi czas nie otrzymano odpowiedzi na to pytanie, dam częściową odpowiedź na pierwszą część pytania:

Co wiadomo na temat (minimalnego) rozpoznawania automatów $X^∗$ dla skończonego kodu $X$ ?

Biorąc pod uwagę skończony zestaw słów $X$ The kwiat automat z $X^*$ jest skończonym niedeterministycznym automatem $\mathcal{A} = (Q, A, E, I, F)$ , gdzie $Q = \{1, 1\} \cup \{ (u, v) \in A^+ \times A^+ \mid uv \in X \}$ , $I = F = \{(1,1)\}$ , z czterema rodzajami przejść:

\begin{aligned} (u, a v) & \overset{a}{⟶} (u a, v) such that u a v \in X, (u, v) \neq (1, 1) \\ (u, a) & \overset{a}{⟶} (1, 1) such that u a \in X, u \neq 1 \\ (1, 1) & \overset{a}{⟶} (a, v) such that a v \in X, v \neq 1 \\ (1, 1) & \overset{a}{⟶} (1, 1) such that a \in X} \end{aligned}

$\begin{align*} (u, av) &\enspace{\buildrel{a} \over\longrightarrow}\enspace (ua, v) \text{ such that } uav \in X,\ (u, v) \neq (1,1) \\ (u, a) &\enspace{\buildrel{a} \over\longrightarrow}\enspace (1, 1) \text{ such that } ua \in X,\ u \neq 1 \\ (1, 1) &\enspace{\buildrel{a} \over\longrightarrow}\enspace(a, v) \text{ such that } av \in X,\ v \neq 1\\ (1, 1) &\enspace{\buildrel{a} \over\longrightarrow}\enspace (1, 1) \text{ such that } a \in X \bigr\} \end{align*}$ Łatwo zauważyć, że ten automat rozpoznaje

X^{*}

$X^*$ . Na przykład jeśli

A = {a, b}

$A= \{a, b\}$ i

X = {a, b a, a a b, a b a}

$X = \{a, ba, aab, aba\}$ , automat do kwiatów

X^{*}

$X^*$ jest następujący

$\qquad\qquad\qquad$

Przypomnijmy, że automat jest jednoznaczny, jeśli przy dwóch stanach $p$ i $q$ i słowo $w$ , istnieje co najwyżej jedna ścieżka z $p$ do $q$ z etykietą $w$ . Następnie obowiązuje następujący wynik:

Twierdzenie [1, Thm 4.2.2]. Zestaw $X$ jest kodem dla automatu kwiatowego $X^*$ jest jednoznaczny.

Automat do kwiatów ma również właściwość algebraiczną, co czyni go względnie zbliżonym do automatu minimalnego. Ta właściwość obowiązuje dla dowolnego zbioru skończonego $X$ , ale łatwiej jest stwierdzić, pozbywając się pustego słowa, to znaczy biorąc pod uwagę język jako podzbiór $A^+$ zamiast $A^*$ .

Przypomnij sobie, że skończona półgrupa $R$ jest lokalnie trywialne, jeśli dla każdego idempotenta $e \in R$ , $eRe = \{e\}$ . Morfizm $\pi:R \to S$ jest lokalnie trywialne, jeśli dla każdego idempotenta $e$ w $S$ , półgrupa $\pi^{-1}(e)$ jest lokalnie trywialne.

Półgrupa przejściowa $T$ automatu kwiatowego $X^+$ nazywa się kwiat półgrupa od $X^+$ . Od $T$ rozpoznaje $L^+$ , istnieje przypuszczalny morfizm $\pi$ od $T$ na półgrupę składniową $S$ z $X^+$ .

Twierdzenie . Morfizm $\pi:T \to S$ jest lokalnie trywialne.

Ważną konsekwencją tego wyniku jest to, że półgrupa kwiatowa i półgrupa składniowa mają taką samą liczbę regularnych $\mathcal{J}$ -klasy.

Bibliografia

[ 1 ] J. Berstel, D. Perrin, C. Reutenauer, Codes and Automata . Encyklopedia matematyki i jej zastosowania, 129. Cambridge University Press, Cambridge, 2010. xiv + 619 s. ISBN: 978-0-521-88831-8

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