Informatiker Board | Suchergebnis

Informatiker Board » Suche » Suchergebnis

» Hallo Gast [Anmelden|Registrieren]

Zeige Beiträge 1 bis 4 von 4 Treffern

Autor

Beitrag

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

C3P0

Antworten:	3
Hits:	5.813

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

Forum: Automatentheorie

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.

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

C3P0

Antworten:	3
Hits:	5.813

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

Forum: Automatentheorie

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.

Thema: zeigen, dass keine reguläre sprache - pumping lemma

C3P0

Antworten:	1
Hits:	3.942

RE: zeigen, dass keine reguläre sprache - pumping lemma 04.05.2011 14:37

Forum: Theoretische Informatik

Hallo,
nimm mal an, dass L regulär ist. Dann gibt es einen endlichen Automaten, der L akzeptiert. Dieser Automat habe k Zustände. Mit dem Wort a^k kommt man dann bei wenigstens einem Zustand zweimal vorbei, man läuft also einen Kreis der Länge $[latex] l \geq 1 [/latex]$ . Jetzt müsste der Automat das Wort $[latex]a^k b^{k-l}[/latex]$ akzeptieren. Daraus kannst du einen Widerspruch erhalten.

Thema: Automaten, kürzestes unterscheidendes Wort

C3P0

Antworten:	0
Hits:	3.502

Automaten, kürzestes unterscheidendes Wort 04.05.2011 14:05

Forum: Theoretische Informatik

Meine Frage:
Hallo zusammen,
ich bin bei der Vorbereitung auf meine Prüfung zur theoretischen Informatik auf folgende Frage gestoßen:

Für einen bliebigen deterministischen endlichen Automaten ist die Länge des kürzesten, zwei Zustände [latex]z_1[/latex]

und

unterscheidenden Wortes stets kleiner gleich |Z|-1, wobei Z die Menge der Zustände ist.

Es soll also für inäquivalente Zustände stets ein Wort w mit $[latex] |w| \leq |Z|-1[/latex]$ geben, für das o.B.d.A. $[latex]f(z_1,w) \in Z_f [/latex]$ und $[latex]f(z_2,w) \notin Z_f [/latex]$ , wobei [latex]Z_f [/latex]

die Menge der Finalzustände ist.

Meine Ideen:
Ich habe schon mehrere Ansätze ausprobiert, komme aber irgendwie nicht zum Ziel.
Als erstes habe ich natürlich bemerkt, dass man mit einem Wort w mit $[latex]|w| \geq |Z|[/latex]$ immer irgendwo einen Kreis im Automaten läuft. Das Problem ist nur, dass ich diese Schlaufe hier nicht so ohne Weiteres "rausschneiden" kann. Wenn ich von [latex]z_1[/latex]

aus mit w in einen Finalzustand laufe, kann ich das dann zwar auch mit einem kürzeren Wort, dieses könnte mich dann aber dummerweise von [latex]z_2 [/latex]

aus auch in einen Finalzustand führen, was ich ja nicht möchte. Außerdem gibt es durchaus Beispiele, in denen man Schlaufen laufen muss, um zwei Zustände zu unterscheiden. Oder übershe ich hier irgendwas?

Als nächstes habe ich per Kreuzproduktkonstruktion einen Automaten gebastelt, der genau die unterscheidenden Wörter akzeptiert. Damit erhalte ich aber im Wesentlichen nur [latex]|w| < |Z|^2 [/latex]

, die Abschätzung kann man noch ein klein wenig verbessern, aber an $[latex] |w| \leq |Z|-1[/latex]$ komme ich so nicht heran. Alternativ kann man sich auch direkt den Minimierungsalgorithmus ansehen, dann erhält man dieselbe Abschätzung.

Zuletzt habe ich mir mal den Minimalautomaten angeguckt, o.B.d.A. kann ich ja zu diesem übergehen. Das könnte auch so gedacht sein, da der erste Teil der Aufgabe lautete: Zeigen Sie, dass in einem Minimalautomaten je zwei verschiedene Zustände inäquivalent sind. Also müsste ich jetzt zeigen können, dass es zu je zwei Äquivalenzklassen der [u] und [v] der Nerode-Relation ein w gibt, sodass o.B.d.A. $[latex]uw \in L[/latex]$ und $[latex]vw \notin L [/latex]$ (L die vom Automaten akzeptierte Sprache), wobei w weniger Buchstaben hat, als die Nerode-Relation Äquivalenzklassen hat. Das ist aber eigentlich nur eine Umformulierung des eigentlichen Problems und hilft mir wenig weiter.

Kann man einen dieser Ansätze retten, oder muss man ganz anders rangehen?

Bin für jede Hilfe dankbar!

LG

Zeige Beiträge 1 bis 4 von 4 Treffern