Theoretische Informatik: Konstruktion eines NEA's?

... komplette Frage anzeigen

2 Antworten

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 bewerten Vielen Dank für Deine Bewertung

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

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von Donlaurus
30.01.2016, 15:40

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.

0

Was möchtest Du wissen?