Zusammenfassung
Automaten und Maschinen haben unterschiedliche Leistungsfähigkeit. Jedem Typ eines Automaten oder einer Maschine lässt sich dann die jeweils erkannte Sprache zuordnen:
Typ
Erkannte Sprachen
Es hat sich herausgestellt:
Jede reguläre Sprache ist kontextfrei,
aber nicht jede kontextfreie Sprache ist regulär.Damit sind die regulären Sprachen echt enthalten in der Menge der kontextfreien Sprachen.
Ebenso sind die kontextfreien Sprachen echt enthalten in der Menge der kontextsensitiven Sprachen.
Die Formalen Sprachen sind somit hierarchisch angeordnet (Chomski-Hierarchie) .