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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

1 Pluspunkt 0 Minuspunkte
84 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?
in Band I, Kapitel 2 von Dozent (10.1m Punkte)  

2 Antworten

0 Pluspunkte 0 Minuspunkte
 
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
von Dozent (10.1m Punkte)  
0 Pluspunkte 0 Minuspunkte
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
von Dozent (10.1m Punkte)  
0 0
Ich hab es leider noch nicht ganz kapiert - woher weiß man nun zu welcher Chomsky-Sprachklasse die Sprache gehört?
...