Informatiker Board | Druckvorschau: Kontextfreie Grammatik

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
-- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
--- Kontextfreie Grammatik (http://www.informatikerboard.de/board/thread.php?threadid=461)

Geschrieben von H4wk am 20.11.2008 um 22:13:

Kontextfreie Grammatik

Hallo!

Ich könnte einen guten Tipp für folgende Aufgabe brauchen.

Zeigen sie, dass das Komplement der nicht kontextfreien Sprache $[latex]L=\{ a^nb^nc^n: n \geq 1 \} [/latex]$ kontextfrei ist.

Muss ich dafür eine kontextfreie Grammatik konstruieren, oder gibt es eine andere Möglichkeit.
Wenn ich die Grammatik konstruieren muss wäre ich auch da für einen Tipp sehr dankbar, da ich bisher immer bei dem Versuch gescheitert bin, da entweder nicht alle oder zu viele Wörter ableitbar waren...

Danke im Vorraus!