Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:automaten:sprachtypen:start [06.03.2023 09:51] – [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 0 und Typ 1 Sprachen können von Turingmaschinen erkannt werden.))
-  * **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.
+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 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''
+{{ :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:*}}