SLP Notizen

Teil II
Kapitel 13: Sprache und Komplexität

Inhalt

1. Die Chomsky-Hierarchie
• reguläre Sprachen < kontextfreie Sprachen < kontextsensitive Sprachen < Turing-äquivalente (berechenbare) Sprachen
• A → xB | x; < A → α; < αAβ → αγβ, mit γ ≠ ε; < α → β, mit α ≠ ε
2. Warum Sprache nicht regulär ist
• center-embedded Strukturen (zentralrekursiv?)
• entsprechen aⁿbⁿ, was nicht regulär ist (Pumping-Lemma)
• Morphologie: staunen -> erstaunen -> erstaunlich, aber nicht staunen -> staunlich
• erfordert also, dass die Grundform "staun" zweifach vorhanden ist
3. Ist Sprache kontextfrei?
• Schweizerdeutsch ist es nicht, es enthält Strukturen die aⁿb^mcⁿd^m entsprechen
4. Komplexität in der menschlichen Sprachverarbeitung
• grundsätzlich ist beliebig tiefe Rekursion erlaubt (Kompetenz)
• tatsächlich bereiten tiefe Strukturen Schwierigkeiten (Performanz)
• Schwierigkeit der Analyse vermutlich durch Speicherbeschränkung (vor allem neuer, nicht integrierter Information)

letzte Änderung: 12. August 2006.