- Wasn kontextfrei und was nicht?
- Wir können das auch wieder mit einem Pumping-Lemma beweisen
- Leider gibt es kein eqiv zum satz von nerode
- Einige algorithmische Problems für kontextfeie Sprachen lassen sich schon effizient lösen
- Wir wollen sowas für Kontextfreie Sprachen finden
- Das kontextfreie pumpinglemma wird genau so wie das "normale" sein, von der Sturktur her
- beim Kontextfreien wird die grundidee sein:
- Wenn wir einen langen ableitungsbaum haben
- wird es einen langen pfad geben, auf dem sich variablen wiederholen
- und was auch immer dazwischen ist, das pumpen wir dann auf
- oder wir lassen das halt komplett weg
- aber egal was wir tun, am ende isat das Wort immernoch in der Sprache