Formale Sprache: Unterschied zwischen den Versionen
Keine Bearbeitungszusammenfassung |
Keine Bearbeitungszusammenfassung |
||
| Zeile 9: | Zeile 9: | ||
Für eine formale Sprache gelten folgende Grundeigenschaften: | Für eine formale Sprache gelten folgende Grundeigenschaften: | ||
- '''Eindeutige Wortzugehörigkeit:''' Für jedes Wort <math>w \in \Sigma^*</math> gilt eindeutig entweder <math>w \in L</math> (das Wort gehört zur Sprache) oder <math>w \notin L</math> (das Wort gehört nicht zur Sprache). | |||
- '''Formale Regeln statt Bedeutung:''' Anders als bei natürlichen Sprachen entscheiden ausschließlich die formalen Bildungsregeln (die Syntax) über die Zugehörigkeit eines Wortes zu <math>L</math>; eine inhaltliche Bedeutung spielt keine Rolle. | |||
- '''Umfang:''' Eine formale Sprache <math>L</math> kann endlich viele oder unendlich viele Wörter enthalten. Auch die leere Menge <math>L = \emptyset</math> (kein einziges Wort ist gültig) und die Gesamtmenge <math>L = \Sigma^*</math> (jedes Wort über <math>\Sigma</math> ist gültig) sind formale Sprachen. | |||
==Alphabet und Wort== | ==Alphabet und Wort== | ||
| Zeile 26: | Zeile 26: | ||
Zwei spezielle Sprachen werden leicht verwechselt: | Zwei spezielle Sprachen werden leicht verwechselt: | ||
- Die Sprache <math>L_1 = \{\varepsilon\}</math> enthält genau '''ein''' Wort, nämlich das leere Wort <math>\varepsilon</math>. | |||
- Die leere Sprache <math>L_2 = \emptyset = \{\}</math> enthält '''kein einziges''' Wort. | |||
==Beschreibung formaler Sprachen== | ==Beschreibung formaler Sprachen== | ||
Eine formale Sprache lässt sich auf vier Arten beschreiben: | Eine formale Sprache lässt sich auf vier Arten beschreiben: | ||
- '''Aufzählung:''' Alle Wörter der Sprache werden einzeln in Mengenklammern aufgelistet. Das ist nur bei endlichen Sprachen möglich. | |||
- '''Mengenschreibweise:''' Eine mathematische oder sprachliche Bedingung legt fest, welche Wörter zur Sprache gehören, in der Form <math>L = \{w \in \Sigma^* \mid \text{Bedingung an } w\}</math>. Das eignet sich auch für unendliche Sprachen. | |||
- '''Automat:''' Ein [[Endlicher Automat|Automat]] <math>A</math> prüft ein Eingabewort Schritt für Schritt und akzeptiert es oder lehnt es ab. Die Menge aller von <math>A</math> akzeptierten Wörter ist die Sprache <math>L(A)</math>. | |||
- '''Grammatik:''' Eine [[Formale Grammatik|Grammatik]] <math>G</math> erzeugt Wörter mithilfe von Produktionsregeln. Die Menge aller aus dem Startsymbol ableitbaren Wörter ist die Sprache <math>L(G)</math>. | |||
Die [[Chomsky-Hierarchie]] ordnet formale Sprachen nach der Form ihrer Grammatikregeln in vier Klassen ein. Jeder Klasse ist ein passendes Automatenmodell zugeordnet, das genau die Sprachen dieser Klasse erkennt. | Die [[Chomsky-Hierarchie]] ordnet formale Sprachen nach der Form ihrer Grammatikregeln in vier Klassen ein. Jeder Klasse ist ein passendes Automatenmodell zugeordnet, das genau die Sprachen dieser Klasse erkennt. | ||
| Zeile 41: | Zeile 41: | ||
===Sprache als Menge angeben=== | ===Sprache als Menge angeben=== | ||
[[Datei:DEA Kaffeeautomat vollständig.png|mini|Vollständiger DEA des Kaffeeautomaten]] | [[Datei:DEA Kaffeeautomat vollständig.png|mini|Vollständiger DEA des Kaffeeautomaten]] | ||
Ein Kaffeeautomat sammelt den Kaffeesatz in einem Satzfach. Das Satzfach ist bei genau 4 Einheiten voll. Ein Kaffee <math>K</math> zählt 1 Einheit, ein Espresso <math>E</math> zählt 2 Einheiten. Das Eingabealphabet lautet <math>\Sigma = \{K | Ein Kaffeeautomat sammelt den Kaffeesatz in einem Satzfach. Das Satzfach ist bei genau 4 Einheiten voll. Ein Kaffee <math>K</math> zählt 1 Einheit, ein Espresso <math>E</math> zählt 2 Einheiten. Das Eingabealphabet lautet <math>\Sigma = \{K; E\}</math>. | ||
Gesucht ist die formale Sprache <math>L \subseteq \Sigma^*</math> aller Tastenkombinationen, die das Satzfach ohne Überlauf exakt füllen. In Mengenschreibweise lautet die Sprache: | Gesucht ist die formale Sprache <math>L \subseteq \Sigma^*</math> aller Tastenkombinationen, die das Satzfach ohne Überlauf exakt füllen. In Mengenschreibweise lautet die Sprache: | ||
:<math>L = \{w \in \{K | :<math>L = \{w \in \{K; E\}^* \mid \text{Die Summe der Einheiten in } w \text{ beträgt genau } 4\}</math> | ||
Ein Wort gehört genau dann zu <math>L</math>, wenn sich die Einheiten seiner Zeichen zu 4 addieren. Genau fünf Wörter aus <math>\Sigma^*</math> erfüllen diese Bedingung: | Ein Wort gehört genau dann zu <math>L</math>, wenn sich die Einheiten seiner Zeichen zu 4 addieren. Genau fünf Wörter aus <math>\Sigma^*</math> erfüllen diese Bedingung: | ||
| Zeile 65: | Zeile 65: | ||
Da die Sprache endlich ist, lässt sie sich vollständig durch Aufzählung ihrer fünf Elemente angeben: | Da die Sprache endlich ist, lässt sie sich vollständig durch Aufzählung ihrer fünf Elemente angeben: | ||
:<math>L = \{KKKK | :<math>L = \{KKKK; EE; EKK; KEK; KKE\}</math> | ||
Alle anderen Wörter über <math>\Sigma</math> gehören nicht zu <math>L</math>. Der im Bild dargestellte Automat akzeptiert mit seinem Endzustand <math>q_4</math> genau die Wörter von <math>L</math>. Sein Aufbau wird im Beispiel [[Deterministischer endlicher Automat#Kaffeeautomat als vollständigen DEA angeben|Kaffeeautomat als vollständigen DEA angeben]] hergeleitet. | Alle anderen Wörter über <math>\Sigma</math> gehören nicht zu <math>L</math>. Der im Bild dargestellte Automat akzeptiert mit seinem Endzustand <math>q_4</math> genau die Wörter von <math>L</math>. Sein Aufbau wird im Beispiel [[Deterministischer endlicher Automat#Kaffeeautomat als vollständigen DEA angeben|Kaffeeautomat als vollständigen DEA angeben]] hergeleitet. | ||
===Wortzugehörigkeit prüfen=== | ===Wortzugehörigkeit prüfen=== | ||
Ob ein Wort <math>w \in \Sigma^*</math> zur Sprache <math>L = \{KKKK | Ob ein Wort <math>w \in \Sigma^*</math> zur Sprache <math>L = \{KKKK; EE; EKK; KEK; KKE\}</math> aus dem vorigen Beispiel gehört, entscheidet die Summe seiner Kaffeesatz-Einheiten (sie muss exakt 4 betragen): | ||
- '''<math>KEK \in L</math>:''' Das Wort besteht aus drei Zeichen (<math>|KEK| = 3</math>) und liefert <math>1 + 2 + 1 = 4</math> Einheiten. Das Satzfach ist genau voll (der Automat endet im Endzustand <math>q_4</math>), also gehört <math>KEK</math> zur Sprache <math>L</math>. | |||
- '''<math>EEK \notin L</math>:''' Das Wort hat die Länge <math>|EEK| = 3</math> und liefert <math>2 + 2 + 1 = 5</math> Einheiten. Das Satzfach läuft über (der Automat wechselt in den Fehlerzustand <math>q_5</math>), also gehört <math>EEK</math> nicht zu <math>L</math>. | |||
- '''<math>KK \notin L</math>:''' Das Wort hat die Länge <math>|KK| = 2</math> und liefert <math>1 + 1 = 2</math> Einheiten. Das Satzfach ist noch nicht voll (der Automat bleibt im Zustand <math>q_2</math> stehen), also gehört <math>KK</math> nicht zu <math>L</math>. | |||
- '''<math>\varepsilon \notin L</math>:''' Das leere Wort enthält kein Zeichen (<math>|\varepsilon| = 0</math>) und liefert 0 Einheiten. Das Satzfach bleibt leer (der Automat verbleibt im Startzustand <math>q_0</math>). Es gilt zwar <math>\varepsilon \in \Sigma^*</math>, aber <math>\varepsilon \notin L</math>. | |||
[[Kategorie:Formale Sprachen]] | [[Kategorie:Formale Sprachen]] | ||
[[Kategorie:AHR I Informatik LK]] | [[Kategorie:AHR I Informatik LK]] | ||