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]] | ||
Version vom 10. November 2026, 09:22 Uhr
Programme und Maschinen prüfen Eingaben nach festen Regeln. Eine formale Sprache legt genau fest, welche Zeichenfolgen zulässig sind.
Definition
Es sei [math]\displaystyle{ \Sigma }[/math] ein Alphabet (eine endliche, nicht leere Menge von Zeichen) und [math]\displaystyle{ \Sigma^* }[/math] die Menge aller endlichen Wörter, die sich aus den Zeichen von [math]\displaystyle{ \Sigma }[/math] bilden lassen (einschließlich des leeren Wortes [math]\displaystyle{ \varepsilon }[/math]).
Eine formale Sprache [math]\displaystyle{ L }[/math] über dem Alphabet [math]\displaystyle{ \Sigma }[/math] ist eine beliebige Teilmenge von [math]\displaystyle{ \Sigma^* }[/math]:
- [math]\displaystyle{ L \subseteq \Sigma^* }[/math]
Für eine formale Sprache gelten folgende Grundeigenschaften: - Eindeutige Wortzugehörigkeit: Für jedes Wort [math]\displaystyle{ w \in \Sigma^* }[/math] gilt eindeutig entweder [math]\displaystyle{ w \in L }[/math] (das Wort gehört zur Sprache) oder [math]\displaystyle{ 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]\displaystyle{ L }[/math]; eine inhaltliche Bedeutung spielt keine Rolle. - Umfang: Eine formale Sprache [math]\displaystyle{ L }[/math] kann endlich viele oder unendlich viele Wörter enthalten. Auch die leere Menge [math]\displaystyle{ L = \emptyset }[/math] (kein einziges Wort ist gültig) und die Gesamtmenge [math]\displaystyle{ L = \Sigma^* }[/math] (jedes Wort über [math]\displaystyle{ \Sigma }[/math] ist gültig) sind formale Sprachen.
Alphabet und Wort
Zeichen und Alphabet
Ein Zeichen ist ein einzelnes, unteilbares Symbol, etwa ein Buchstabe, eine Ziffer oder ein Sonderzeichen. Ein Alphabet [math]\displaystyle{ \Sigma }[/math] ist eine endliche, nicht leere Menge solcher Zeichen ([math]\displaystyle{ \Sigma \neq \emptyset }[/math]). Seine Elemente heißen auch Buchstaben des Alphabets.
Wort und Wortlänge
Ein Wort [math]\displaystyle{ w }[/math] über [math]\displaystyle{ \Sigma }[/math] ist eine endliche Folge von Zeichen aus [math]\displaystyle{ \Sigma }[/math]. Die Wortlänge [math]\displaystyle{ |w| }[/math] eines Wortes [math]\displaystyle{ w }[/math] gibt die Anzahl seiner Zeichen an.
Die Verkettung (Konkatenation) zweier Wörter [math]\displaystyle{ u \in \Sigma^* }[/math] und [math]\displaystyle{ v \in \Sigma^* }[/math] hängt [math]\displaystyle{ v }[/math] direkt an [math]\displaystyle{ u }[/math] an und ergibt das Wort [math]\displaystyle{ uv \in \Sigma^* }[/math]. Dabei addieren sich die Wortlängen: [math]\displaystyle{ |uv| = |u| + |v| }[/math]. Die Reihenfolge der Zeichen ist wesentlich: [math]\displaystyle{ uv }[/math] und [math]\displaystyle{ vu }[/math] sind im Allgemeinen verschiedene Wörter ([math]\displaystyle{ uv \neq vu }[/math]).
Leeres Wort
Das leere Wort [math]\displaystyle{ \varepsilon }[/math] enthält kein Zeichen, es gilt [math]\displaystyle{ |\varepsilon| = 0 }[/math]. Es gehört zu jedem [math]\displaystyle{ \Sigma^* }[/math] ([math]\displaystyle{ \varepsilon \in \Sigma^* }[/math]), weil es keine Zeichen enthält, die außerhalb von [math]\displaystyle{ \Sigma }[/math] liegen, ist aber selbst kein Zeichen des Alphabets ([math]\displaystyle{ \varepsilon \notin \Sigma }[/math]). Beim Verketten verändert es ein Wort nicht: [math]\displaystyle{ w\varepsilon = \varepsilon w = w }[/math].
Zwei spezielle Sprachen werden leicht verwechselt: - Die Sprache [math]\displaystyle{ L_1 = \{\varepsilon\} }[/math] enthält genau ein Wort, nämlich das leere Wort [math]\displaystyle{ \varepsilon }[/math]. - Die leere Sprache [math]\displaystyle{ L_2 = \emptyset = \{\} }[/math] enthält kein einziges Wort.
Beschreibung formaler Sprachen
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]\displaystyle{ L = \{w \in \Sigma^* \mid \text{Bedingung an } w\} }[/math]. Das eignet sich auch für unendliche Sprachen. - Automat: Ein Automat [math]\displaystyle{ A }[/math] prüft ein Eingabewort Schritt für Schritt und akzeptiert es oder lehnt es ab. Die Menge aller von [math]\displaystyle{ A }[/math] akzeptierten Wörter ist die Sprache [math]\displaystyle{ L(A) }[/math]. - Grammatik: Eine Grammatik [math]\displaystyle{ G }[/math] erzeugt Wörter mithilfe von Produktionsregeln. Die Menge aller aus dem Startsymbol ableitbaren Wörter ist die Sprache [math]\displaystyle{ 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.
Beispiele
Sprache als Menge angeben

Ein Kaffeeautomat sammelt den Kaffeesatz in einem Satzfach. Das Satzfach ist bei genau 4 Einheiten voll. Ein Kaffee [math]\displaystyle{ K }[/math] zählt 1 Einheit, ein Espresso [math]\displaystyle{ E }[/math] zählt 2 Einheiten. Das Eingabealphabet lautet [math]\displaystyle{ \Sigma = \{K; E\} }[/math].
Gesucht ist die formale Sprache [math]\displaystyle{ L \subseteq \Sigma^* }[/math] aller Tastenkombinationen, die das Satzfach ohne Überlauf exakt füllen. In Mengenschreibweise lautet die Sprache:
- [math]\displaystyle{ 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]\displaystyle{ L }[/math], wenn sich die Einheiten seiner Zeichen zu 4 addieren. Genau fünf Wörter aus [math]\displaystyle{ \Sigma^* }[/math] erfüllen diese Bedingung:
| Wort [math]\displaystyle{ w }[/math] | Wortlänge [math]\displaystyle{ |w| }[/math] | Berechnung der Einheiten |
|---|---|---|
| [math]\displaystyle{ KKKK }[/math] | 4 | [math]\displaystyle{ 1 + 1 + 1 + 1 = 4 }[/math] |
| [math]\displaystyle{ EE }[/math] | 2 | [math]\displaystyle{ 2 + 2 = 4 }[/math] |
| [math]\displaystyle{ EKK }[/math] | 3 | [math]\displaystyle{ 2 + 1 + 1 = 4 }[/math] |
| [math]\displaystyle{ KEK }[/math] | 3 | [math]\displaystyle{ 1 + 2 + 1 = 4 }[/math] |
| [math]\displaystyle{ KKE }[/math] | 3 | [math]\displaystyle{ 1 + 1 + 2 = 4 }[/math] |
Da die Sprache endlich ist, lässt sie sich vollständig durch Aufzählung ihrer fünf Elemente angeben:
- [math]\displaystyle{ L = \{KKKK; EE; EKK; KEK; KKE\} }[/math]
Alle anderen Wörter über [math]\displaystyle{ \Sigma }[/math] gehören nicht zu [math]\displaystyle{ L }[/math]. Der im Bild dargestellte Automat akzeptiert mit seinem Endzustand [math]\displaystyle{ q_4 }[/math] genau die Wörter von [math]\displaystyle{ L }[/math]. Sein Aufbau wird im Beispiel Kaffeeautomat als vollständigen DEA angeben hergeleitet.
Wortzugehörigkeit prüfen
Ob ein Wort [math]\displaystyle{ w \in \Sigma^* }[/math] zur Sprache [math]\displaystyle{ 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]\displaystyle{ KEK \in L }[/math]: Das Wort besteht aus drei Zeichen ([math]\displaystyle{ |KEK| = 3 }[/math]) und liefert [math]\displaystyle{ 1 + 2 + 1 = 4 }[/math] Einheiten. Das Satzfach ist genau voll (der Automat endet im Endzustand [math]\displaystyle{ q_4 }[/math]), also gehört [math]\displaystyle{ KEK }[/math] zur Sprache [math]\displaystyle{ L }[/math]. - [math]\displaystyle{ EEK \notin L }[/math]: Das Wort hat die Länge [math]\displaystyle{ |EEK| = 3 }[/math] und liefert [math]\displaystyle{ 2 + 2 + 1 = 5 }[/math] Einheiten. Das Satzfach läuft über (der Automat wechselt in den Fehlerzustand [math]\displaystyle{ q_5 }[/math]), also gehört [math]\displaystyle{ EEK }[/math] nicht zu [math]\displaystyle{ L }[/math]. - [math]\displaystyle{ KK \notin L }[/math]: Das Wort hat die Länge [math]\displaystyle{ |KK| = 2 }[/math] und liefert [math]\displaystyle{ 1 + 1 = 2 }[/math] Einheiten. Das Satzfach ist noch nicht voll (der Automat bleibt im Zustand [math]\displaystyle{ q_2 }[/math] stehen), also gehört [math]\displaystyle{ KK }[/math] nicht zu [math]\displaystyle{ L }[/math]. - [math]\displaystyle{ \varepsilon \notin L }[/math]: Das leere Wort enthält kein Zeichen ([math]\displaystyle{ |\varepsilon| = 0 }[/math]) und liefert 0 Einheiten. Das Satzfach bleibt leer (der Automat verbleibt im Startzustand [math]\displaystyle{ q_0 }[/math]). Es gilt zwar [math]\displaystyle{ \varepsilon \in \Sigma^* }[/math], aber [math]\displaystyle{ \varepsilon \notin L }[/math].