Czy istnieje dobrze określona operacja podziału automatów skończonych?

15

Tło:

Biorąc pod uwagę dwa deterministyczne automaty skończone A i B, tworzymy iloczyn C, pozwalając, by stany w C były iloczynem kartezjańskim stanów w A i stanów w B. Następnie wybieramy stany przejściowe, początkowe i końcowe, aby język został zaakceptowany przez C to przecięcie języków dla A i B.

Pytania:

(1) Czy możemy „podzielić” C przez B, aby znaleźć A? Czy jest nawet wyjątkowy, aż do izomorfizmu? Dbamy o diagramy stanu, a nie o języki tutaj i poniżej. Dlatego nie zezwalamy na kompresowanie diagramów stanów w celu zmniejszenia liczby stanów.

(2) Jeśli A jest unikalny, czy istnieje skuteczny algorytm do jego znalezienia?

(3) Czy każdy deterministyczny automat skończony ma unikalną faktoryzację na „liczby pierwsze”. Liczba pierwsza oznacza tutaj automat, którego nie można rozłożyć na fakt, to znaczy napisany jako produkt 2 mniejszych automatów.

Pracuj z @MichaelWehar

fl.formal-languages automata-theory dfa

— Whosyourjay
źródło

5

Klasycznym rozkładem jest teoria Krohna-Rhodesa - wiele do zobaczenia.

2

Rozważ pochodne Brzozowskiego. en.wikipedia.org/wiki/Brzozowski_derivative

— Vijay D

2

@halfTrucker Teoria Krohna-Rhodesa dotyczy produktu wieńcowego. OP pyta o produkt kartezjański.

— scaaahu

2

Dzięki @halfTrucker, to jest naprawdę interesujące! Jak mówi scaaahu, szukam produktu kartezjańskiego, ale twoje referencje są nadal świetne.

— Whosyourjay,

8

Spójrz na ten artykuł MFCS 2013 , który bada kompozycję w automatach. Być może to pomoże.

— Shaull
źródło

2

+1 za link. Cytując z dyskusji na temat artykułu, Podczas gdy ogólny przypadek jest nadal otwarty , wydaje się, że artykuł bada tylko przypadek automatu permutacji. Czy pojawiły się jakieś nowsze opracowania dotyczące ogólnych przypadków? Mam na myśli w sensie produktu kartezjańskiego? (Teoria Krohna-Rhodesa dotyczy produktu wieńcowego) Dzięki.

— scaaahu

3

Nie znam żadnych ostatnich wydarzeń. Mogę powiedzieć, że nie było bezpośrednich działań następczych w związku z tym dokumentem. Może to jednak wskazywać, że problem nie jest wcale łatwy.

— Shaull,

4

Podajmy oczywisty sposób na odzyskanie jednego „czynnika” automatu produktu. Jeśli i oznacza automat produktu, to jeśli zdefiniujemy czyli tylko zapomina o $\mathcal A_i = (Q_i, \delta_i, q_{0i}, F_i), i = 1,2$ $\mathcal A = \mathcal A_1 \times \mathcal A_2$

π_{1} ((q, q^{'})) := q

$\pi_1( (q, q') ) := q$

A_{2}

$\mathcal A_2$ lub rzutując na drugi komponent, mamy

, także jeśli chcemy wiedzieć

wybierz trochę

i oblicz w automacie iloczynu

Q_{1} = π (Q_{1} \times Q_{2})

$Q_1 = \pi(Q_1\times Q_2)$

δ_{1} (q, x)

$\delta_1(q,x)$

q^{'} \in Q_{2}

$q' \in Q_2$

, a więc, że może także odzyskiwać przejścia w

.

π ((δ_{1} (q, x), δ_{2} (q^{'}, x)) = δ_{1} (q, x)

$\pi((\delta_1(q,x), \delta_2(q', x)) = \delta_1(q,x)$

A_{1}

$\mathcal A_1$

Więc jeśli wiemy, że automat jest kartezjańskim (lub zewnętrznym) automatem produktu, możemy łatwo odzyskać czynniki.

Ale myślę, że nie to masz na myśli w odniesieniu do innych pytań. Pojawiają się tutaj dwa pytania (dalej przez automatyczny izomorfizm mam na myśli izomorficzny jako graf stanu, tj. Bez względu na stany początkowe lub końcowe, jak powiedziałeś, język nie jest tutaj tak bardzo istotny):

A_{1} \times \dots \times A_{k} ≅ B_{1} \times \dots \times B_{l}

$\mathcal A_1 \times \ldots \times \mathcal A_k \cong \mathcal B_1 \times \ldots \times \mathcal B_l$

A_{i}, B_{j}

$\mathcal A_i, \mathcal B_j$

k = l

$k = l$

A_{i} ≅ B_{π (i)}

$\mathcal A_i \cong \mathcal B_{\pi(i)}$

π : {1, \dots k} \to {1, \dots k}

$\pi : \{1,\ldots k \}\to \{1,\ldots k \}$

$\mathcal A, \mathcal B$ $\mathcal C$ $\mathcal A = \mathcal B \times \mathcal C$

Łatwo jest ustalić niezbędne warunki, ale nie widzę żadnych łatwych wystarczających kryteriów, aby jakiś automat był czynnikiem innym.

π_{1} ((δ_{1} (q, x), δ_{2} (q^{'}, x)) = δ_{1} (q, x) = δ_{1} (π_{1} (q, q^{'}), x)

$\pi_1( (\delta_1(q, x), \delta_2(q', x)) = \delta_1(q,x) = \delta_1(\pi_1(q,q'), x)$

q \in Q_{1}, q^{'} \in Q_{2}

$q \in Q_1, q' \in Q_2$

π

$\pi$

A_{1} \times A_{2}

$\mathcal A_1 \times \mathcal A_2$

A_{2}

$\mathcal A_2$

$\mathcal A$ $\mathcal B$ $\mathcal B$ $\mathcal A$

$\mathcal B$ $\mathcal A$

$M$ $N$ $M$ $N$

H. Straubing, P. Weil Wprowadzenie do automatów skończonych i ich związek z logiką,

Strona internetowa kursu z dużą ilością informacji.

Uwaga : Istnieje również inne pojęcie „ ilorazu ”, patrz wikipedia: iloraz automat , ale jest to tylko reguła dla stanów zwijania i stosowana w algorytmach uczenia się / wnioskowania języka lub minimalizacji stanu.

— StefanH
źródło