Informatiker Board | Druckvorschau: Wie Zustände für NOT-EQUAL deterministischen Automat herausfinden?

Geschrieben von InfoBiensche am 11.05.2011 um 09:55:

Wie Zustände für NOT-EQUAL deterministischen Automat herausfinden?

Meine Frage:
Ich kann mir einfach keinen Automaten für diese Sprache vorstellen...
NOT-EQn = {xy | x element aus {0,1}^n, x!=y}
Ich soll zeigen, dass jeder deterministische Automat mindestens 2^n Zustände hat. Und wie würde ein nichtdeterministischer Automat aussehen?

Meine Ideen:
Ich muss mir ja sozusagen "merken" was mein x war, damit ich es mit dem y vergleichen kann, aber wenn ich für jede eingabe einen neuen Zustand aufmache werden das viel zu viele...

Geschrieben von C3P0 am 11.05.2011 um 11:14:

RE: Wie Zustände für NOT-EQUAL deterministischen Automat herausfinden?

Hallo,
der Trick an der Aufgabe ist, dass dort $[latex] x \in \{0,1\}^n[/latex]$ und nicht $[latex] x \in \{0,1\}^*[/latex]$ steht, x hat also die Länge n (oder höchstens die Länge n, je nachdem, wie ihr {0,1}^n definiert habt). Insbesondere kommen nur endlich viele Wörter für x in Frage. Dann hast du kein Problem, dir in Zuständen zu merken, was du bisher gelesen hast.

Um zu zeigen, dass es deterministisch nicht mit weniger als 2^n Zuständen geht, schau dir mal den Minimalautomaten an und zeige, dass der wenigstens so viele Zustände hat.

Geschrieben von InfoBiensche am 11.05.2011 um 11:50:

RE: Wie Zustände für NOT-EQUAL deterministischen Automat herausfinden?

Aber mir den Automaten vorzustellen IST ja gerade mein Problem. Wenn ich von jedem Zustand aus einen 1 Übergang und einen 0 Übergang mache in einen neuen Zustand, dann habe ich allein um mir x zu merken (Summe für i von 0 bis n von 2^i) Zustände. Also es gibt 2^n mögliche Wörter die x und y sein können, aber wie kann mir das ausreichen als Zustände im Automat??

Geschrieben von C3P0 am 11.05.2011 um 12:11:

RE: Wie Zustände für NOT-EQUAL deterministischen Automat herausfinden?

Man könnte das z.B. so implementieren: Sei e das leere Wort und [latex] z_e[/latex]

der Startzustand, dann gehst du von [latex]z_e [/latex]

mit einer 1 in den Zustand [latex] z_1[/latex]

, von dort z.B. mit einer 0 in $[latex] z_{10}[/latex]$ usw., mit dem Wort x läufst du also in den Zustand [latex] z_x[/latex]

und hast dir somit das x im Zustand gemerkt. Jetzt musst du dir noch überlegen, wie du von hier aus mit y vergleichst, das kannst du aber ähnlich machen.

Aber eigentlich ist es doch gar nicht deine Aufgabe, einen Automaten konkret anzugeben, du sollst doch nur zeigen, dass jeder dterministische Automat mindestens [latex] 2^n[/latex]

Zustände hat. Dazu schau dir mal den Minimalautomaten und die Nerode-Relation an.
Alternativ kannst du auch annehmen, dass es weniger als [latex] 2^n[/latex]

Zustände gibt, dann landest du nach dem Einlesen zweier verschiedener Wörter [latex]x_1 [/latex]

und

im selben Zustand, das kannst du dann auch direkt zum Widerspruch führen.