Gibt es eine genau definierte Divisionsoperation für endliche Automaten?

Hintergrund:

Bei zwei deterministischen endlichen Automaten A und B bilden wir das Produkt C, indem wir die Zustände in C das kartesische Produkt von Zuständen in A und Zuständen in B sein lassen C ist der Schnittpunkt der Sprachen für A und B.

Fragen:

(1) Können wir C durch B "teilen", um A zu finden? Ist A einmalig bis zum Isomorphismus? Wir kümmern uns um die Zustandsdiagramme, nicht um die Sprachen hier und unten. Daher dürfen die Zustandsdiagramme nicht komprimiert werden, um die Anzahl der Zustände zu verringern.

(2) Wenn A eindeutig ist, gibt es einen effizienten Algorithmus, um es zu finden?

(3) Hat jeder deterministische endliche Automat eine eindeutige Faktorisierung in "Primzahlen"? Eine Primzahl bedeutet hier einen Automaten, der nicht berücksichtigt werden kann, dh als Produkt von 2 kleineren Automaten geschrieben ist.

Arbeite mit @MichaelWehar

fl.formal-languages automata-theory dfa Wer bist du?
quelle

Die klassische Zerlegung ist die Krohn-Rhodes-Theorie - viel zu sehen.

Betrachten wir Brzozowski-Derivate. en.wikipedia.org/wiki/Brzozowski_derivative

Vijay D

@halfTrucker Krohn-Rhodes-Theorie befasst sich mit Kranzprodukt. Das OP fragt nach kartesischem Produkt.

Scaaahu

Danke @halfTrucker, das ist wirklich interessant! Wie Scaaahu sagt, suche ich kartesisches Produkt, aber Ihre Referenz ist immer noch großartig.

Whosyourjay

Antworten:

Schauen Sie sich dieses MFCS 2013-Papier an , das die Komposition in Automaten untersucht. Vielleicht hilft es.

Shaull
quelle

+1 für den Link. Aus der Diskussion des Artikels zitiert: Während der allgemeine Fall noch offen ist , scheint es, dass der Artikel nur den Fall von Permutationsautomaten untersucht. Gibt es neuere Entwicklungen für allgemeine Fälle? Ich meine im Sinne von kartesischem Produkt? (Krohn-Rhodes-Theorie befasst sich mit Kranzprodukt) Danke.

Scaaahu

Ich kenne keine neuen Entwicklungen. Ich kann Ihnen sagen, dass es keine direkten Folgemaßnahmen zu diesem Papier gab. Dies kann jedoch als Hinweis darauf dienen, dass das Problem in der Tat nicht einfach ist.

Shaull

Geben wir einen offensichtlichen Weg, um einen "Faktor" des Produktautomaten wiederzugewinnen. Wenn und den Produktautomaten bezeichnet, dann definieren wir dh einfach vergessen $\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$ oder auf die zweite Komponente projiziert, haben wir

, auch wenn wir

kennen wollen, wählen Sie einige

und berechnen Sie im Produktautomaten

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$

, daher können wir auch den Übergang in

wiederherstellen.

π ((δ_{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$

Wenn wir also wissen, dass ein Automat ein kartesischer (oder externer) Produktautomat ist, können wir die Faktoren leicht wiederfinden.

Aber ich denke, das ist nicht das, was Sie in Bezug auf Ihre anderen Fragen im Sinn haben. Hier stellen sich zwei Fragen (im Folgenden meine ich mit Automatenisomorphismus isomorph als Zustandsgraph, dh ohne Berücksichtigung von Anfangs- oder Endzuständen, wie Sie sagten, die Sprache ist hier nicht so sehr von Belang):

1) Ist diese Zerlegung bei jedem Automaten, der zu einem Produktautomaten isomorph ist (dh auf irgendeine Weise zerlegt werden könnte), einer endlichen Anzahl von Automaten im wesentlichen einzigartig? (vorausgesetzt, die Faktoren könnten nicht weiter zerlegt werden, sonst offensichtlich nicht). Genauer gesagt, wenn für nicht zusammensetzbare Automaten

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 \}$

2) Bei zwei beliebigen Automaten $\mathcal A, \mathcal B$ $\mathcal C$ $\mathcal A = \mathcal B \times \mathcal C$

Es ist leicht, die notwendigen Bedingungen dafür abzuleiten, aber ich sehe keine einfachen ausreichenden Kriterien dafür, dass ein Automat ein Faktor eines anderen ist.

π_{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 Einführung in endliche Automaten und deren Verknüpfung mit der Logik,

Kurswebsite mit vielen Informationen.

Bemerkung : Es gibt auch einen anderen Begriff von " Quotientierung ", siehe Wikipedia: Quotientautomat , aber dies ist nur eine Regel für das Zusammenfallen von Zuständen und wird in Lern- / Sprachinferenzalgorithmen oder bei der Zustandsminimierung verwendet.

StefanH
quelle