Wie kann ich beweisen, dass eine gegebene Sprache vom Typ-2 ist?
Hier ist mein Ansatz. Ich bilde eine Typ-2 Grammatik zu dieser Sprache. Es gilt, dass zu jeder Typ-2 Grammatik eine Typ-2 Grammatik in CNF existiert. Wäre das ein Ansatz um zu zeigen, dass eine Sprache vom Typ-2 ist?
Gibt es noch andere Möglichkeiten? Ich könnte theoretisch auch einen PDA aufzeichnen oder?
1 Antwort
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Informatik, Theoretische Informatik, Informatik
Üblicherweise nutzt man das Pumping-Lemma für kontextfreie Sprachen.
Wenn du eine Typ-2 Grammatik zu einer Sprache bilden kannst, dann ist diese Sprache eine Typ-2 Sprache, somit kontextfrei (evtl. hat sie aber auch die Bedingungen für eine Typ-3 Grammatik oder sonstiges).