NFA mit exponentieller Anzahl von Zuständen bei Deteminisierung

10

Wie kann ich ein Beispiel für einen DFA mit Zuständen erstellen , wobei der äquivalente NFA Zustände hatNatürlich sollte der Statussatz des EDA alle Teilmengen des Statussatzes des NFA enthalten, aber ich weiß nicht, wie ich anfangen soll. Irgendwelche Vorschläge, um mich auf den richtigen Weg zu bringen? $2^n$ $n$

automata finite-automata saadtaame
quelle

Diese Frage ist etwas unklar. Im Allgemeinen gibt es unendlich viele äquivalente DFAs für eine bestimmte reguläre Sprache und unendlich viele äquivalente NFAs für eine bestimmte reguläre Sprache. Wenn Sie minimale DFAs mit Zuständen wünschen , ist dies nicht immer möglich, da verschiedene NFAs dieselbe Sprache erkennen und unterschiedliche Anzahlen von Zuständen haben können, aber demselben minimalen DFA entsprechen. Wenn Sie zusätzlich nur "minimale" NFAs berücksichtigen möchten, wird dies etwas interessanter ...

2^{n}

$2^n$

Patrick87

1

Patrick, ich denke, das OP bedeutet ein Beispiel, bei dem der minimale DFA exponentiell größer ist als der minimale NFA.

Yuval Filmus

@ Patrick87 Ich suche keinen Algorithmus. Ich möchte nur ein Beispiel für ein Maschinenpaar: DFA mit Zuständen und NFA mit Zuständen, die dieselbe Sprache akzeptieren.

2^{n}

$2^n$

n

$n$

Saadtaame

@saadtaame: Das ist trivial: Nimm einen beliebigen DFA und füge genügend Zustände hinzu, um zu erreichen . Interessantes Beispiel sind solche, bei denen das minimale äquivalente DFA ebenso viele Zustände aufweist.

2^{n}

$2^n$

Raphael

1

Beachten Sie, dass der Wikipedia-Artikel zur DFA-Minimierung auf geeignete Beispiele verweist (obwohl Sie die kleine NFA selbst herausfinden müssen).

Raphael

17

Das Standardbeispiel ist die Sprache aller Wörter über einem Alphabet der Größe , die nicht alle verschiedenen Buchstaben enthalten. Es gibt eine NFA, die mit Zuständen akzeptiert (oder Zustände, wenn Sie mehrere Startzustände zulassen): Erraten Sie zuerst einen fehlenden Buchstaben und gehen Sie dann (mit einer Bewegung) in einen akzeptierenden Zustand mit Selbstschleifen für alle Buchstaben außer . $L$ $A$ $n$ $L$ $n+1$ $n$ $a$ $\epsilon$ $A$

Jeder DFA für erfordert mindestens Zustände. Dies kann mit dem Myhill-Nerode-Theorem gesehen werden. Sei zwei verschiedene Teilmengen von und Wörtern, die alle und nur die Buchstaben in enthalten. Nehmen Sie ohne Verlust der Allgemeinheit an und lassen Sie . Dann ist während . $L$ $2^n$ $S_1,S_2$ $A$ $w(S_1),w(S_2)$ $S_1,S_2$ $a \in S_1 \setminus S_2$ $w = w(A-a)$ $w(S_1)w \notin L$ $w(S_2)w \in L$

Yuval Filmus
quelle

10

Dies ist eine Übung in dem Buch "Finite Automata" von Mark V. Lawson, Heriot-Watt University, Edinburgh, Seite 68:

Sei . Zeigen Sie, dass die Sprache von einem nicht deterministischen Automaten mit Zuständen erkannt werden kann . Zeigen Sie, dass jeder deterministische Automat, der diese Sprache erkennt, mindestens Zustände haben muss. Dieses Beispiel zeigt, dass eine exponentielle Zunahme der Anzahl von Zuständen beim Übergang von einem nicht deterministischen Automaten zu einem entsprechenden deterministischen Automaten manchmal unvermeidbar ist. $n \geq 1$ $(0+1)^\ast 1(0+1)^{n−1}$ $n+1$ $2^n$

MK Dadsetani
quelle

10

Ich gehe davon aus, dass Sie meinen, dass der optimale DFA Zustände hat. Vielleicht bringt dir das nicht Zustände, aber es ist . $2^n$ $2^n$ $\Omega(2^n)$

Aus "Communication Complexity" von Kushilevitz und Nisan in Übung 12.6:

" Betrachten Sie für eine konstante [nicht negative ganze Zahl] die (endliche) Sprache ." $c$ $L_c = \{ww\mid w \in \{0,1\}^c\}$

und das Buch fordert Sie weiterhin auf zu beweisen, dass Sie eine Co-NFA finden können, die erkennt , die -Zustände verwendet, und dass Sie für einen DFA keine besseren als -Zustände erzielen können. $L_c$ $O(c)$ $\Omega(2^c)$

Timothy Sun.
quelle

Der Nachweis des zweiten Teils "erfordert" auch Kommunikationskomplexität, sodass dies möglicherweise nicht für Ihre Zwecke geeignet ist.

Timothy Sun

Danke für die Antwort! Was meinst du mit Co-NFA?

Saadtaame

Wechseln Sie in der Definition eines NFA grundsätzlich zwischen "Akzeptieren" und "Ablehnen". Das heißt, wenn keiner der möglichen Pfade zu einem Ablehnungsstatus führt, akzeptieren Sie, andernfalls lehnen Sie ab.

Timothy Sun

Tatsächlich folgt die Untergrenze ziemlich leicht von Myhill-Nerode. (Tatsächlich können Sie so etwas wie .) Aber meine Co-NFA verwendet -Zustände.

2^{c}

$2^c$

(c + 1) 2^{c}

$(c+1)2^c$

Θ (c^{2})

$\Theta(c^2)$

Yuval Filmus

Endliche Sprachen sind in dieser Hinsicht etwas langweilig. Siehe auch hier .

Raphael

8

Dies ist eine späte Antwort, aber anscheinend hat niemand die optimale Lösung gegeben. Nehmen Sie , und , mit Diese NFA ist Ein aus zwei Buchstaben bestehendes Alphabet hat Zustände, nur einen Anfangs- und einen Endzustand, und sein äquivalenter minimaler DFA hat Zustände. $A = \{a, b\}$ $Q_n = \{0, 1, \ldots, n-1\}$ ${\cal A}_n = (Q_n, A, E_n, \{0\}, \{0\})$

E_{n} = {(i, a, i + 1) ∣ 0 ⩽ i ⩽ n - 1} \cup {(n - 1, a, 0)} \cup {(i, b, i) ∣ 1 ⩽ i \leq n - 1} \cup {(i, b, 0) ∣ 1 ⩽ i ⩽ n - 1}}

$E_n = \{(i, a, i+1) \mid 0 \leqslant i \leqslant n-1\} \cup \{(n-1, a, 0)\} \cup \{(i, b, i) \mid 1 \leqslant i \leq n-1\} \cup \{(i, b, 0) \mid 1 \leqslant i \leqslant n-1\}\}$

n

$n$

2^{n}

$2^n$

J.-E. Stift
quelle

3

Sehr schlau! Die von diesem Automaten akzeptierte Sprache ist , wobei aus allen Wörtern besteht, die den Buchstaben höchstens Mal enthalten.

(a^{n} + a W_{n - 1} b)^{*}

$(a^n + aW_{n-1}b)^*$

W_{n - 1}

$W_{n-1}$

a

$a$

n - 1

$n-1$

Yuval Filmus

2

@ yuval-filmus Dieses Beispiel gehört nicht mir. Ich wollte eine Referenz geben, aber im Moment erinnere ich mich nicht, wo ich sie gesehen habe.

J.-E.

NFA mit exponentieller Anzahl von Zuständen bei Deteminisierung

Antworten: