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

11.05.2011, 09:55	Auf diesen Beitrag antworten »
InfoBiensche	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...


11.05.2011, 11:14	Auf diesen Beitrag antworten »
C3P0	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.
11.05.2011, 11:50	Auf diesen Beitrag antworten »
InfoBiensche	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??
11.05.2011, 12:11	Auf diesen Beitrag antworten »
C3P0	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 der Startzustand, dann gehst du von mit einer 1 in den Zustand , von dort z.B. mit einer 0 in $[latex] z_{10}[/latex]$ usw., mit dem Wort x läufst du also in den Zustand 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 Zustände hat. Dazu schau dir mal den Minimalautomaten und die Nerode-Relation an. Alternativ kannst du auch annehmen, dass es weniger als Zustände gibt, dann landest du nach dem Einlesen zweier verschiedener Wörter und im selben Zustand, das kannst du dann auch direkt zum Widerspruch führen.
Anzeige

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »