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==
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 [[Wort|Wörter]] über <math>\Sigma</math> einschließlich des leeren Wortes. Anders als bei natürlichen Sprachen entscheiden nur die Regeln, die Bedeutung spielt keine Rolle.
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 von Zeichen. Seine Elemente heißen auch Buchstaben des Alphabets.
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 Länge <math>|w|</math> eines Wortes <math>w</math> ist die Anzahl seiner Zeichen.
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 gilt <math>|uv| = |u| + |v|</math>. Die Reihenfolge ist wesentlich: <math>uv</math> und <math>vu</math> sind im Allgemeinen verschiedene Wörter.
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 ist ein Wort über jedem Alphabet, gehört aber nicht zum Alphabet. Beim Verketten ändert es nichts: <math>w\varepsilon = \varepsilon w = w</math>.
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 stehen einzeln in einer Menge. Das geht nur bei endlichen Sprachen.
* '''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 geht auch bei unendlichen Sprachen.
* '''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 ein Wort ab. Die Menge aller akzeptierten Wörter ist die Sprache <math>L(A)</math>.
* '''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 mit Regeln. Die Menge aller erzeugten Wörter ist die Sprache <math>L(G)</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 die Sprachen nach der Form der Grammatikregeln in Klassen. Jeder Klasse ist ein Automatenmodell zugeordnet, das ihre Sprachen 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.


==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 vier Einheiten voll. Ein Kaffee K zählt 1 Einheit, ein Espresso E zählt 2 Einheiten. Das Eingabealphabet ist <math>\Sigma = \{K, E\}</math>.
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 zur Sprache, wenn es das Satzfach genau füllt, also zusammen 4 Einheiten ergibt. Fünf Wörter erfüllen das:
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>
|}
|}


Die Sprache ist endlich, deshalb genügt die Aufzählung:
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 Automat im Bild akzeptiert genau die Wörter von <math>L</math>. Sein Aufbau steht im Beispiel [[Deterministischer endlicher Automat#Kaffeeautomat als vollständigen DEA angeben|Kaffeeautomat als vollständigen DEA angeben]].
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, zeigt die Summe seiner Einheiten. Sie muss genau 4 betragen.
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. Die Länge ist <math>|KEK| = 3</math>.
* '''<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 hat 0 Einheiten, es gilt <math>|\varepsilon| = 0</math>. Das Satzfach bleibt leer.
* '''<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]]