Wie vergleicht man Sprachklassen? |
| |
| |
| |
Können für die Komponenten einer Grammatik Entsprechungen beim Automaten gefunden werden und umgekehrt? |
|
Wie kann man vorgehen, um heraus zu finden,
inwieweit die Sprachklassen, die von einem bestimmten Automatentyp bzw. einem bestimmten Grammatiktyp ausgehen, übereinstimmen.
Eine Möglichkeit wäre, alle Sprachen, die von einem Automaten erkannt werden, aufzuzählen.
Außerdem zählt man alle Sprachen auf, die mit dem vermuteten Grammatiktyp generiert werden können.
Nun vergleicht man schließlich diese beiden Mengen miteinander.
Findet man auch nur eine Sprache, die nur in einer der beiden Mengen vorhanden ist, dann kann man mit dem Vergleich aufhören,
denn offensichtlich stimmen die Mengen nicht überein.
Hat man jede einzelne Sprache der einen Menge in der anderen Menge gefunden, so kann man schlussfolgern,
dass Grammatiktyp und Automatentyp Sprachen der gleichen Sprachklasse beschreiben.
HALT! Da stimmt doch was nicht!
Wie gelingt es mir; alle Sprachen aufzuzählen? Wie kann ich mir sicher sein, dass das alle sind?
Es könnte doch unendlich viele Sprachen in einer Sprachklasse geben.
Und selbst wenn ich alle finden könnte, wie vergleiche ich sie dann?
Außerdem erwiesen sich Grammatiken als elegantes und v.a. genaueres Werkzeug, um Sprachen zu beschreiben.
Eine Aufzählung der Sprachen einer Klasse würde auf eine Aufzählung ihrer Grammatiken hinauslaufen.
Somit wird ein generelles Verfahren gebraucht, mit dem ich zeigen kann, dass es für jede Grammatik diesen Typs
einen Automaten des bestimmten Typs gibt und umgekehrt: dass es für jedes Programm eines Automaten des bestimmten Typs
eine Grammatik in der vorgegebenen Form gibt.
|
1
2
Übersicht: Sprachklassen