Frage von Donlaurus, 37

Theoretische Informatik: Konstruktion eines NEA's?

Hallo zusammen, ich sitze gerade an einer THI aufgabe und komme nicht weiter:

Zeigen Sie durch Beschreibung der Konstruktion eines NEA, dass die Sprache L = {w ∈ {0,1}*| w hat k Stellen vor dem letzten Zeichen eine 0 stehen} von einem nicht- deterministischen endlichen Automaten mit k+1 Zuständen erkannt werden kann. Geben Sie weiterhin eine Abschätzung, wieviele Zustände der entsprechende deterministische Automat enthält.

Also ich habe das so verstanden, dass z.B. das Wort 011 (also k=2) von einem Automat mit 3 Zuständen erkannt werden muss. Mein Problem ist, ich schaffe es einfach nicht mit dieser Anzahl an Zuständen einen Automat zu konstruieren, sondern nur mit k+2..

Hat vielleicht von Euch jemand eine Idee?

Danke schonmal im Voraus;)

Antwort
von Melvissimo, 24

Ich sehe ein, dass man leicht einen Automaten mit k+2 Zuständen erzeugen kann und auch mir ist unklar, wie es mit k+1 Zuständen gehen soll. Genauer gesagt glaube ich, es geht gar nicht.

  • Beispiel: k = 0.

Dann darf der Automat nur einen Zustand Z haben. Da z.B. das Wort "0" in der Sprache liegt, muss Z ein Finalzustand sein. Da z.B. das Wort "10" auch in der Sprache liegt, muss es einen Übergang für die Eingabe 1 geben. D.h.

(Z,1) ~> Z muss im Automaten möglich sein.

Damit ist aber auch das Wort "1" vom Automaten akzeptiert, was aber definitiv nicht in der Sprache liegen sollte...

Antwort
von 1frozenice1, 24

Ich glaube dass du einen kleinen Denkfehler hast. Das Wort 011 müsste doch k=3 haben? 
Per Definition sind k die Anzahl der Stellen des Wortes. 
{1111101,01,00000,00,001} gehört zur Sprache.
{1,11,011,0,011,11011} gehört nicht zur Sprache

Kommentar von Donlaurus ,

Es wird nur eine Aussage gemacht, dass " w hat k Stellen vor dem letzten Zeichen eine 0 stehen". Das bedeutet nicht dass |w|=k sondern dass eben eben k stellen vor der letzten ne 0 ist...sonst wärs einfach und man könnte auch einen DEA dafür angeben.

Keine passende Antwort gefunden?

Fragen Sie die Community