Formale Sprache: Unterschied zwischen den Versionen
Die Seite wurde neu angelegt: „Programme und Maschinen prüfen Eingaben nach festen Regeln. Eine formale Sprache legt genau fest, welche Zeichenfolgen zulässig sind. ==Definition== Eine formale Sprache <math>L</math> über einem Alphabet <math>\Sigma</math> ist eine Teilmenge <math>L \subseteq \Sigma^*</math>. <math>\Sigma^*</math> ist die Menge aller Wörter über <math>\Sigma</math> einschließlich des leeren Wortes. Anders als bei natürlichen Sprachen entscheiden nur…“ |
Keine Bearbeitungszusammenfassung |
||
| Zeile 2: | Zeile 2: | ||
==Definition== | ==Definition== | ||
Es sei <math>\Sigma</math> ein [[Alphabet]] (eine endliche, nicht leere [[Menge]] von [[Zeichen]]) und <math>\Sigma^*</math> die Menge aller endlichen [[Wort|Wörter]], die sich aus den Zeichen von <math>\Sigma</math> bilden lassen (einschließlich des leeren Wortes <math>\varepsilon</math>). | |||
Für jedes Wort <math>w \in \Sigma^*</math> gilt entweder <math>w \in L</math> oder <math>w \notin L</math>. | Eine '''formale Sprache''' <math>L</math> über dem Alphabet <math>\Sigma</math> ist eine beliebige Teilmenge von <math>\Sigma^*</math>: | ||
:<math>L \subseteq \Sigma^*</math> | |||
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== | ||
===Zeichen und Alphabet=== | ===Zeichen und Alphabet=== | ||
Ein [[Zeichen]] ist ein einzelnes Symbol, etwa ein Buchstabe, eine Ziffer oder ein Sonderzeichen. Ein Alphabet <math>\Sigma</math> ist eine endliche, nicht leere Menge | Ein [[Zeichen]] ist ein einzelnes, unteilbares Symbol, etwa ein Buchstabe, eine Ziffer oder ein Sonderzeichen. Ein [[Alphabet]] <math>\Sigma</math> ist eine endliche, nicht leere Menge solcher Zeichen (<math>\Sigma \neq \emptyset</math>). Seine Elemente heißen auch Buchstaben des Alphabets. | ||
===Wort und Wortlänge=== | ===Wort und Wortlänge=== | ||
Ein [[Wort]] über <math>\Sigma</math> ist eine endliche Folge von Zeichen aus <math>\Sigma</math>. Die | Ein [[Wort]] <math>w</math> über <math>\Sigma</math> ist eine endliche Folge von Zeichen aus <math>\Sigma</math>. Die Wortlänge <math>|w|</math> eines Wortes <math>w</math> gibt die Anzahl seiner Zeichen an. | ||
Die Verkettung zweier Wörter <math>u</math> und <math>v</math> hängt <math>v</math> an <math>u</math> an und ergibt das Wort <math>uv</math>. Dabei | Die Verkettung (Konkatenation) zweier Wörter <math>u \in \Sigma^*</math> und <math>v \in \Sigma^*</math> hängt <math>v</math> direkt an <math>u</math> an und ergibt das Wort <math>uv \in \Sigma^*</math>. Dabei addieren sich die Wortlängen: <math>|uv| = |u| + |v|</math>. Die Reihenfolge der Zeichen ist wesentlich: <math>uv</math> und <math>vu</math> sind im Allgemeinen verschiedene Wörter (<math>uv \neq vu</math>). | ||
===Leeres Wort=== | ===Leeres Wort=== | ||
Das leere Wort <math>\varepsilon</math> enthält kein Zeichen, es gilt <math>|\varepsilon| = 0</math>. Es | Das leere Wort <math>\varepsilon</math> enthält kein Zeichen, es gilt <math>|\varepsilon| = 0</math>. Es gehört zu jedem <math>\Sigma^*</math> (<math>\varepsilon \in \Sigma^*</math>), weil es keine Zeichen enthält, die außerhalb von <math>\Sigma</math> liegen, ist aber selbst kein Zeichen des Alphabets (<math>\varepsilon \notin \Sigma</math>). Beim Verketten verändert es ein Wort nicht: <math>w\varepsilon = \varepsilon w = w</math>. | ||
Zwei Sprachen werden leicht verwechselt: Die Sprache <math>\{\varepsilon\}</math> enthält ein Wort, nämlich das leere Wort. Die leere Sprache <math>\emptyset</math> enthält kein Wort. | 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 | * '''Aufzählung:''' Alle Wörter der Sprache werden einzeln in Mengenklammern aufgelistet. Das ist nur bei endlichen Sprachen möglich. | ||
* '''Mengenschreibweise:''' Eine Bedingung legt fest, welche Wörter zur Sprache gehören, in der Form <math>L = \{w \in \Sigma^* \mid \text{Bedingung}\}</math>. Das | * '''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> akzeptiert oder lehnt | * '''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 | * '''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 | 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== | ==Beispiele== | ||
===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 | 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: | |||
:<math>L = \{w \in \{K, E\}^* \mid \text{Die Summe der Einheiten in } w \text{ beträgt genau } 4\}</math> | |||
Ein Wort gehört | 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: | ||
{| class="wikitable" style="text-align:center" | {| class="wikitable" style="text-align:center" | ||
! Wort !! Einheiten | ! Wort <math>w</math> !! Wortlänge <math>|w|</math> !! Berechnung der Einheiten | ||
|- | |- | ||
| KKKK || 1 + 1 + 1 + 1 = 4 | | <math>KKKK</math> || 4 || <math>1 + 1 + 1 + 1 = 4</math> | ||
|- | |- | ||
| EE || 2 + 2 = 4 | | <math>EE</math> || 2 || <math>2 + 2 = 4</math> | ||
|- | |- | ||
| EKK || 2 + 1 + 1 = 4 | | <math>EKK</math> || 3 || <math>2 + 1 + 1 = 4</math> | ||
|- | |- | ||
| KEK || 1 + 2 + 1 = 4 | | <math>KEK</math> || 3 || <math>1 + 2 + 1 = 4</math> | ||
|- | |- | ||
| KKE || 1 + 1 + 2 = 4 | | <math>KKE</math> || 3 || <math>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>L = \{KKKK, EE, EKK, KEK, KKE\}</math> | :<math>L = \{KKKK, EE, EKK, KEK, KKE\}</math> | ||
Alle anderen Wörter über <math>\Sigma</math> gehören nicht zu <math>L</math>. Der | 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 zur Sprache <math>L</math> aus dem vorigen Beispiel gehört, | 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>: 1 + 2 + 1 = 4 Einheiten. Das Satzfach ist genau voll | * '''<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>: 2 + 2 + 1 = 5 Einheiten. Das Satzfach läuft über. | * '''<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>: 1 + 1 = 2 Einheiten. Das Satzfach ist nicht voll. | * '''<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 | * '''<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]] | ||