Nächste Seite: Ableitungsbaum Aufwärts: theorie Vorherige Seite: Minimierung von endlichen Automaten   Inhalt

Kontextfreie Sprachen (CFG)

---

Unterabschnitte

• Ableitungsbaum
  • Rechtsableitung / Linksableitung
  • Eindeutigkeit / Mehrdeutigkeit
  
  
• Nutzlose Variablen
  • Definition
  • Algorithmus
  
  
• Chomsky Normalform (CNF)
  • Definition
  • Algorithmus zur Eliminierung der Kettenregeln
  • Algorithmus zur Erzeugung der Chomsky-Normalform
  • Beispiel
  • Größe der CNF
  
  
• CYK-Algorithmus für das Wortproblem
  • Algorithmus
  • Laufzeit
  • Beispiele
  
  
• Pumping Lemma für kontextfreie Sprachen
  • Satz
  • Beweis
  
  
• Abschlußeigenschaften
• Griebach Normalform
  • Satz
  • Konstruktionsalgorithmus
  
  
• Kellerautomaten
  • Definition: Nichtdeterministischer Kellerautomat (NKA)
  • Konfiguration, Notation der Übergangsfunktion und Konfigurationswechsel
  • Akzeptanzverhalten
  • Akzeptanz durch Endzustand Akzeptanz durch leeren Keller
  • Akzeptanz durch leeren Keller Akzeptanz durch Endzustand
  • Kontextfreie Grammatik NKA
  • NKA kontextfreie Grammatik
  • NKAs mit zwei Kellern
  • reguläre Sprache kontextfreie Sprache = kontextfreie Sprache

---