|
Wodurch unterscheiden sich Sprachklassen? Welche Eigenschaften besitzt eine Sprachklasse?
- Äquivalente Umformung von Grammatiken
- Normalformen
- Reduzierte Grammatiken
- Abschlusseigenschaften der Sprachklasse
- Wortproblem
Äquivalenz: stark, wenn sowohl die Sprache als auch die den Sätzen zugewiesene Struktur gleich ist;
schwach, wenn zwei Grammatiken die gleiche Sprache generieren, aber den Sätzen dabei unterschiedliche Strukturen zuweisen.
Testen der Zugehörigkeit
|
Abschlusseigenschaften
