Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:automaten:sprachtypen:start [06.03.2023 09:39] – [Einteilung von Sprachen] Frank Schiebel
+++ faecher:informatik:oberstufe:automaten:sprachtypen:start [06.03.2023 10:36] (aktuell) – Frank Schiebel
@@ Zeile 11: / Zeile 11: @@
 {{ :faecher:informatik:oberstufe:automaten:sprachtypen:chie.drawio.png |}}((Die rot umrandeten sind nicht Teil des Bildungsplans im Baden-Württemberg))
-Wie im Schaubild zu erkennen ist, sind die Sprachtypen hierarchisch ineinander enthalten, jede Typ 2 Sprache ist also auch stets vom Typ 0 und vom Typ 1.
+Wie im Schaubild zu erkennen ist, sind die Typen der Grammatiken hierarchisch ineinander enthalten, jede Typ 2 Sprache ist also auch stets vom Typ 0 und vom Typ 1.
-Klassifizierung der Typen:
+==== Klassifizierung der Typen ====
-  * Jede Grammatik ist automatisch vom **Typ 0**. Typ 0 Grammatiken erzeugen "rekursiv aufzählbare Sprachen". Die Produktionen der Grammatik unterliegen hier keinen Regeln, es sind beliebige Zuordnungen möglich:''abcdAABCC -> abAAD''.
+=== Typ 0 ===
-  * Schränkt man die zulässigen Regeln etwas ein, erhält man eine **Typ 1** Grammatik: Hier sind nur Regeln erlaubt, die auf der rechten Seite mindestens gleich lang sind wie auf der linken Seite ((Ausnahme: ''S->ε'' (Leeres Symbol) )). Erlaubt sind also z.B. ''AbNc->abacdABCc'' oder ''Nab -> Naabc'', nicht aber das Beispiel von oben: ''abcdAABCC -> abAAD'' da hier die linke Seite länger ist als die rechte. Typ 1 Grammatiken beschreiben kontextsensitive Sprachen.
-  * **Typ 2** Grammatiken erlauben ausschließlich Regeln der Form ''Genau ein nichtterminales Symbol  ->  Beliebige Kombination aus terminalen und nichtterminalen Symbolen''  Erlaubt: ''A->BC'', ''B->abACba''. Nicht erlaubt: ''AB->abaCD'', ''bA->abACacB''
+Jede Grammatik ist automatisch vom **Typ 0**. Typ 0 Grammatiken erzeugen "rekursiv aufzählbare Sprachen". Die Produktionen der Grammatik unterliegen hier keinen Regeln, es sind beliebige Zuordnungen möglich:''abcdAABCC -> abAAD''.
+{{ :faecher:informatik:oberstufe:automaten:sprachtypen:t0.drawio.png |}}
+=== Typ 1 ===
+Schränkt man die zulässigen Regeln etwas ein, erhält man eine **Typ 1** Grammatik: Hier sind nur Regeln erlaubt, die auf der rechten Seite mindestens gleich lang sind wie auf der linken Seite ((Ausnahme: ''S->ε'' (Leeres Symbol) )). Erlaubt sind also z.B. ''AbNc->abacdABCc'' oder ''Nab -> Naabc'', nicht aber das Beispiel von oben: ''abcdAABCC -> abAAD'' da hier die linke Seite länger ist als die rechte. Typ 1 Grammatiken beschreiben kontextsensitive Sprachen.((Typ 0 und Typ 1 Sprachen können von Turingmaschinen erkannt werden.))
+{{ :faecher:informatik:oberstufe:automaten:sprachtypen:t1.drawio.png |}}
+=== Typ 2 ===
+**Typ 2** Grammatiken erlauben ausschließlich Regeln der Form ''Genau ein nichtterminales Symbol  ->  Beliebige Kombination aus terminalen und nichtterminalen Symbolen''  Erlaubt: ''A->BC'', ''B->abACba''. Nicht erlaubt: ''AB->abaCD'', ''bA->abACacB''. Typ 2 Grammatiken erzeugen kontextfreie Sprachen. Sie können mit Kellerautomaten erkannt werden.
+{{ :faecher:informatik:oberstufe:automaten:sprachtypen:t2.drawio.png |}}
+=== Typ 3 ===
+**Typ 3** Grammatiken erlauben bei jeder Regel auf der rechten Seite nur
+  * ε oder
+  * einzelne Zeichen des Alphabets oder
+  * ein einzelnes Zeichen des Alphabets und danach eine einzelne Variable stehen (rechtsregulär) oder
+  * eine einzelne Variable und danach ein einzelnes Zeichen stehen (linksregulär)
+Erlaubt: ''A->aB'', ''B->c'', ''C->ε'', ''A->Ba''. Verboten: ''A->aBa'', ''C->abD''
+Typ 3 Grammatiken erzeugen reguläre Sprachen, diese können von DEAs erkannt werden.
+{{ :faecher:informatik:oberstufe:automaten:sprachtypen:t3.drawio.png |}}
+===== Dateien =====
+{{simplefilelist>:faecher:informatik:oberstufe:automaten:sprachtypen:*}}