---

Geschrieben von Maltron am 22.01.2016 um 21:01:

  Kellerautomat / Pushdown Verstehe Aufgabenstellung nicht

Guten Abend,

ich schreibe nächste Woche eine Klausur und bin gerade dabei ein paar Übungsaufgaben zu Kellerautomaten(PDA) zu machen.
Nun habe ich zwei Aufgaben bei denen ich mir nicht ganz sicher bin ob ich sie richtig verstehe:

1. Die Menge aller Zeichenreihen aus Nullen und Einsen, derart dass kein Präfix mehr Einsen als Nullen hat. --> Ich bin mir hier nicht ganz sicher über die Bedeutung von Präfix und wie so ein Wort aussehen würde.

2. Die Menge aller Zeichenreihen aus den Symbolen a und b, die für kein w die Form ww haben --> Bedeutet das z.B. keine Wörter der Form {abab, aa, bb, baba}?


Vielen Dank im Voraus für eure Hilfe!

---

Geschrieben von eulerscheZahl am 23.01.2016 um 06:39:

 

1: angenommen, dein Wort ist 01100. Dann sind die Präfixe 0, 01, 011, 0110, 01100.
Bei 011 hast du mehr 1en als 0en, also ist das Wort nicht in der Sprache.

2: ja.

---

Geschrieben von Maltron am 23.01.2016 um 11:28:

 

Okay, dann hab ichs verstanden. Vielen Dank!