Wer kann mir den bei der folgenden Frage weiterhelfen ?
Die verschiedenen Sprachklassen in der Chomsky-Hierarchie (reguläre Sprachen, kontext-
freie Sprachen usw.) haben unterschiedliche Komplexitäten. Beispielsweise lassen sich mit
regulären Sprachen keine korrekten Klammerausdrücke erkennen, während dies mit kon-
textfreien Sprachen geht. Erläutern Sie möglichst präzise, warum das mit regulären Spra-
chen nicht möglich ist.
Danke
Hallo,
regulaere Sprachen koennen durch endliche Automaten erkannt werden. Diese haben nur ein endliches Gedaechtnis. Dadurch kann sich der Automat nur eine endliche Anzahl von oeffnenden Klammern merken. Falls der Klammerausdruck mehr geschachtelte oeffnende Klammern erhaelt, so erkennt der Automat auch nicht korrekte Klammerausdruecke (Anzahl der oeffnenden Klammern ist ungleich Anzahl der schliessenden).
Das ist so die grobe Idee. Die solltest Du dann noch etwas praeziser ausformulieren.
MfG
Richard
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]