Warum ist eine Sprache, die von einem EA erkannt wird, vom Typ 3?

Question

"Wenn es von einem endlichen Automaten erkannt wird, dann ist es doch in erster Linie Typ 3?"

 

Wieso gilt das? Kann man sich keine endlichen Automaten vorstellen, die ohne eine rechtslineare Grammatik auskommen?

Answer 1

Um zu zeigen, dass eine Sprache $L$ zur Sprachklasse $L_i$ gehört, kann man folgende Dinge tun:

1. Eine Grammatik $G$ von Typ $i$ angeben mit $L(G)=L$.
2. Einen entsprechenden Automaten $A$ angeben (Automaten des Typs $i$ sind nämlich äquivalent zu Grammatiken des Typs $i$ in Bezug auf die Sprachmächtigkeit):

• Endlicher Automat für Typ 3,
• Kellerautomat für Typ 2,
• Linear beschränkter Automat (bzw. l. b. Turingmaschine) für Typ 1,
• allgemeine Turingmaschine für Typ 0

mit $L(A)=L$.

1. Für die Klasse $L_3$ kann man außerdem auch einen regulären Ausdruck angeben.

Dann weiß man allerdings immer noch nicht (außer bei Typ 3), ob die Sprache nicht auch in $L_{i+1}$ liegt, da die Klassen ja ineinander enthalten sind. Um zu zeigen, dass $L$ NICHT in $L_3$ bzw. $L_2$ liegt, kann man bspw. das entsprechende Pumping-Lemma benutzen. Dass eine Sprache, die in $L_0$ liegt, nicht in $L_1$ liegt ist schon schwieriger zu zeigen, und darauf will ich jetzt nicht genauer eingehen.

 

Für Beweise, dass eine Sprache nicht in $L_0$ liegt, haben wir allerdings wieder Beispiele in der Vorlesung gehabt. Man kann z.B. mit Diagonalisierung zeigen, dass die Sprache $L_{NA}$ von keiner Turingmaschine erkannt werden kann und somit nicht in $L_0$ liegt.

 

Ein häufiges Missverständnis kommt allerdings beim Halteproblem auf. Dieses liegt nämlich in $L_0$, obwohl man zeigen kann, dass es nicht berechenbar ist. Die Definition von $L_0$ fordert nämlich nicht die Berechenbarkeit eines Problems, sondern nur die Semientscheidbarkeit, und diese ist für das Halteproblem gegeben.

 

Ein gutes Beispiel für diese Methoden zur Einsortierung einer Sprache in die "richtige" Chomsky-Stufe ist die erste Aufgabe vom dritten Heimübungsblatt.

 

Viele Grüße

 

Lukas König

Answer 2

EA und rechtslineare Grammatiken haben zunächst mal nichts mit einander zu tun. Man kann aber zeigen, dass die Modelle äquivalent sind. Trotzdem sind sie voneinander unabhängig. Ihre Aussage hat in dieser Form also keinen Sinn: "Kann man sich keine endlichen Automaten vorstellen, die ohne eine rechtslineare Grammatik auskommen?"

 

Aber etwas umformuliert könnte man sagen: Nein, man kann sich keine endlichen Automaten vorstellen, die eine Sprache erkennen, für die es keine rechtslineare Grammatik gibt.

 

Viele Grüße

 

Lukas König

Comments

Ich hab es leider noch nicht ganz kapiert - woher weiß man nun zu welcher Chomsky-Sprachklasse die Sprache gehört?