Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

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

+1 Punkt
68 Aufrufe
"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?
Gefragt 6, Nov 2014 in Band I, Kapitel 2 von Lukas König Dozent (10,065,100 Punkte)  

2 Antworten

0 Punkte
 
Beste Antwort
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
Beantwortet 6, Nov 2014 von Lukas König Dozent (10,065,100 Punkte)  
0 Punkte
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
Beantwortet 6, Nov 2014 von Lukas König Dozent (10,065,100 Punkte)  
Ich hab es leider noch nicht ganz kapiert - woher weiß man nun zu welcher Chomsky-Sprachklasse die Sprache gehört?
...