Minimieren Sie deterministische endliche Automaten ohne akzeptierende Zustände

8

Ich habe einen endlichen Automaten ohne endgültige / akzeptierende Zustände, also ist F leer. Wie minimiere ich es?

Ich habe dies bei einem Test erhalten und wusste nicht, wie ich das Problem angehen sollte, da der Automat keine akzeptierenden Zustände hatte. Ist ein einzelner Ausgangszustand mit allen Übergängen in sich die richtige Antwort?

automata finite-automata crs12decoder
quelle

5

Ja. Einige Antworten sind so einfach.

Luke Mathieson

es ist dann kein Wandler.

Grijesh Chauhan

@GrijeshChauhan Wo in der Frage haben Sie den Begriff "Wandler" gefunden?

Raphael

6

Ihre Vermutung ist richtig und Sie können sie wie folgt etwas formeller sehen. Sei ein DFA. Die Nerode Kongruenz auf wie folgt definiert ist: $\mathcal{A} = (Q, A, \cdot, q_0, F)$ $\sim$ $Q$ Die Menge der Zustände des Minimalautomaten von ist . Nunwenn die leere Menge, alle Zustände ist sind -Äquivalent und damit hat nur ein Element, sagen wir

p \sim q if and only if, for every word u \in A^{*}, p \cdot u \in F ⟺ q \cdot u \in F

$p \sim q \text{ if and only if, for every word $u \in A^*$, }\ p \cdot u \in F \iff q \cdot u \in F$

A

$\mathcal{A}$

Q / \sim

$Q/{\sim}$

F

$F$

Q

$Q$

\sim

$\sim$

Q / \sim

$Q/{\sim}$

. Sie haben keine Wahl für die Übergänge und somit

für jeden Buchstaben

. Schließlich ist

der Anfangszustand, aber es gibt keinen Endzustand.

Q / \sim = {1}

$Q/{\sim} = \{1\}$

1 \cdot a = 1

$1 \cdot a = 1$

a

$a$

1

$1$

J.-E. Stift
quelle

2

Es ist absolut nicht erforderlich, die Nerode-Kongruenz zu verwenden, um zu beweisen, dass ein Ein-Zustands-Automat für die leere Sprache minimal ist. Es ist ziemlich formal genug zu sagen, dass ein Automat ohne akzeptierende Zustände

akzeptiert und dass ein Ein-Zustands-Automat, der eine bestimmte Sprache akzeptiert, minimal sein muss, da jeder Automat mindestens einen Zustand haben muss.

\emptyset

$\emptyset$

David Richerby

1

@ David-Richerby Ich weiß das genau. Ich habe gerade erwähnt, dass dieses Ergebnis mit der Standarddefinition übereinstimmt, die in Standardkursen angegeben ist.

J.-E.

7

Ein endlicher Automat ohne Endzustände bezeichnet die Sprache L = . Um einen DFA zu minimieren, minimieren wir die Anzahl der Zustände und die angegebene Sprache muss identisch sein. Per Definition von DFA müssen wir also einen Anfangszustand haben $\emptyset$ $q_0$ $| Q | \geq 1$ $q_0$

Renato Sanhueza
quelle

Minimieren Sie deterministische endliche Automaten ohne akzeptierende Zustände

Antworten: