Formale Sprache: Unterschied zwischen den Versionen

Keine Bearbeitungszusammenfassung
Keine Bearbeitungszusammenfassung
Markierung: Manuelle Zurücksetzung
 
(3 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 4: Zeile 4:
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>).
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>).


Eine '''formale Sprache''' <math>L</math> über dem Alphabet <math>\Sigma</math> ist eine beliebige Teilmenge von <math>\Sigma^*</math>:
Eine '''formale Sprache''' <math>L</math> über dem Alphabet <math>\Sigma</math> ist eine beliebige [[Menge#Teilmenge|Teilmenge]] von <math>\Sigma^*</math>:


:<math>L \subseteq \Sigma^*</math>
:<math>L \subseteq \Sigma^*</math>
Zeile 10: Zeile 10:
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).
* '''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.
* '''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 (die Semantik) 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.
* '''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.


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 Sprache <math>\{\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.
* Die leere Sprache <math>\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.
* '''Aufzählung:''' Alle Wörter der Sprache werden einzeln in Mengenklammern aufgelistet und durch Semikolons getrennt. 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.
* '''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>. Der senkrechte Strich wird „für die gilt“ gelesen. Das eignet sich auch für unendliche Sprachen. Vor dem Strich kann statt <math>w</math> auch ein Wortmuster stehen, das den Aufbau der Wörter zeigt, zum Beispiel mit einer [[Wort#Wortpotenz|Wortpotenz]] oder mit einem Platzhalter für ein beliebiges Wort. Hinter dem Strich steht dann, welche Werte die Variablen annehmen dürfen.
* '''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>.
* '''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>.
* '''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.
==Sprachen als Mengen==
Weil formale Sprachen [[Menge|Mengen]] von Wörtern sind, gelten für sie alle Begriffe der Mengenlehre:
* '''Endlich oder unendlich:''' Eine Sprache ist endlich, wenn sie nur endlich viele Wörter enthält. Enthält eine Sprache mindestens ein Wort und gibt es zu jedem ihrer Wörter ein längeres Wort, das ebenfalls zur Sprache gehört, ist sie unendlich.
* '''Teilmenge:''' <math>L_1 \subseteq L_2</math> gilt, wenn jedes Wort aus <math>L_1</math> auch zu <math>L_2</math> gehört. Um zu zeigen, dass diese Beziehung '''nicht''' gilt, genügt ein einziges Wort aus <math>L_1</math>, das nicht in <math>L_2</math> liegt (ein Gegenbeispiel).
* '''Schnitt und Vereinigung:''' Die [[Menge#Schnittmenge|Schnittmenge]] <math>L_1 \cap L_2</math> enthält die Wörter, die zu beiden Sprachen gehören. Die [[Menge#Vereinigungsmenge|Vereinigungsmenge]] <math>L_1 \cup L_2</math> enthält die Wörter, die zu mindestens einer der beiden Sprachen gehören.


==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 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>.
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, E\}^* \mid \text{Die Summe der Einheiten in } w \text{ beträgt genau } 4\}</math>
:<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 71:
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, 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 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, EE, EKK, KEK, KKE\}</math> aus dem vorigen Beispiel gehört, entscheidet die Summe seiner Kaffeesatz-Einheiten (sie muss exakt 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>:''' 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>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>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 [[Deterministischer endlicher Automat#Vollständiger DEA und Fehlerzustand|Fehlerzustand]] <math>q_F</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>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>.
* '''<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>.
===Zeichenfolge außerhalb des Alphabets erkennen===
Eine Zeichenfolge kann aus zwei verschiedenen Gründen nicht zu einer Sprache gehören. Für die Sprache <math>L</math> des Kaffeeautomaten über <math>\Sigma = \{K; E\}</math> zeigt das der Vergleich zweier Eingaben:
* '''<math>KTE</math>:''' Das Zeichen <math>T</math> gehört nicht zum Alphabet (<math>T \notin \Sigma</math>). Die Zeichenfolge ist deshalb gar kein Wort über <math>\Sigma</math> (<math>KTE \notin \Sigma^*</math>) und kann zu keiner Sprache über <math>\Sigma</math> gehören.
* '''<math>KK</math>:''' Alle Zeichen stammen aus dem Alphabet, es gilt <math>KK \in \Sigma^*</math>. Das Wort erfüllt aber die Regel der Sprache nicht, weil es nur 2 Einheiten liefert. Deshalb gilt <math>KK \notin L</math>.
Zuerst wird also geprüft, ob alle Zeichen zum Alphabet gehören, danach, ob das Wort die Regel der Sprache erfüllt.
===Unendliche Sprache in Mengenschreibweise angeben===
Gesucht ist die Sprache <math>L_E</math> aller Bestellfolgen über <math>\Sigma = \{K; E\}</math>, die mindestens einen Espresso enthalten.
* '''Mit einer Bedingung:''' <math>L_E = \{w \in \Sigma^* \mid w \text{ enthält mindestens ein } E\}</math>
* '''Mit einem Wortmuster:''' <math>L_E = \{uEv \mid u \in \Sigma^* \text{ und } v \in \Sigma^*\}</math>. Die Platzhalter <math>u</math> und <math>v</math> stehen für beliebige Wörter über <math>\Sigma</math>, auch für das leere Wort. Dazwischen steht das feste Zeichen <math>E</math>.
Die kürzesten Wörter der Sprache sind <math>E</math> (mit <math>u = \varepsilon</math> und <math>v = \varepsilon</math>), <math>KE</math>, <math>EK</math> und <math>EE</math>. Von den acht Wörtern der Länge 3 gehören alle außer <math>KKK</math> dazu. Das leere Wort gehört nicht dazu, denn es enthält kein <math>E</math>.
Die Sprache ist unendlich: Hängt man an ein Wort aus <math>L_E</math> ein weiteres Zeichen an, entsteht ein längeres Wort, das ebenfalls ein <math>E</math> enthält. Eine Aufzählung aller Wörter ist deshalb nicht möglich. Der passende Automat steht im Beispiel [[Deterministischer endlicher Automat#Akzeptierte Sprache eines DEA beschreiben|Akzeptierte Sprache eines DEA beschreiben]].
===Sprache mit Wortpotenzen angeben===
Mit [[Wort#Wortpotenz|Wortpotenzen]] lassen sich unendliche Sprachen über <math>\Sigma = \{K; E\}</math> kurz angeben. Hinter dem Strich steht, welche Werte der Exponent <math>n</math> annehmen darf.
* '''<math>L_X = \{K^n E \mid n \ge 1\}</math>:''' Für <math>n = 1</math>, <math>n = 2</math> und <math>n = 3</math> entstehen die Wörter <math>KE</math>, <math>KKE</math> und <math>KKKE</math>. Die Sprache enthält alle Wörter aus mindestens einem <math>K</math> und einem abschließenden <math>E</math>. Das Wort <math>E</math> gehört nicht dazu, denn <math>n = 0</math> ist nicht erlaubt.
* '''<math>L_Y = \{(KE)^n \mid n \ge 0\}</math>:''' Hier wird das ganze Wort <math>KE</math> wiederholt. Für <math>n = 0</math>, <math>n = 1</math> und <math>n = 2</math> entstehen <math>\varepsilon</math>, <math>KE</math> und <math>KEKE</math>. Weil <math>n = 0</math> erlaubt ist, gehört das leere Wort zur Sprache.
* '''Vereinigung und Schnitt:''' <math>L_X \cup L_Y</math> enthält alle Wörter, die zu mindestens einer der beiden Sprachen gehören, zum Beispiel <math>\varepsilon</math>, <math>KE</math>, <math>KKE</math> und <math>KEKE</math>. Das Wort <math>KE</math> gehört zu beiden Sprachen, es entsteht jeweils für <math>n = 1</math>. Es ist das einzige gemeinsame Wort: <math>L_X \cap L_Y = \{KE\}</math>.
Die Schreibweise legt für jedes Wort fest, ob es dazugehört. <math>KEK</math> gehört zu keiner der beiden Sprachen: Das Wort endet nicht mit <math>E</math> und ist deshalb weder von der Form <math>K^n E</math> noch eine Wiederholung von <math>KE</math>.
===Leere Sprache und Sprache mit dem leeren Wort unterscheiden===
Über <math>\Sigma = \{K; E\}</math> werden drei Sprachen verglichen:
{| class="wikitable" style="text-align:center"
! Sprache !! Anzahl der Wörter !! Gehört <math>\varepsilon</math> dazu? !! Gehört <math>K</math> dazu?
|-
| <math>\emptyset</math> || 0 || nein || nein
|-
| <math>\{\varepsilon\}</math> || 1 || ja || nein
|-
| <math>\{\varepsilon; K\}</math> || 2 || ja || ja
|}
Die leere Sprache <math>\emptyset</math> enthält gar kein Wort, auch nicht das leere. Die Sprache <math>\{\varepsilon\}</math> ist dagegen nicht leer: Sie enthält ein Wort, und dieses Wort hat die Länge 0.
Am Kaffeeautomaten bedeutet das: Die Sprache <math>\{\varepsilon\}</math> lässt genau eine Bestellfolge zu, nämlich die ohne jeden Tastendruck. Die Sprache <math>\emptyset</math> lässt keine Bestellfolge zu, auch diese nicht. Ein Automat ohne Endzustand akzeptiert kein Wort, seine Sprache ist <math>\emptyset</math>. Ein Automat, dessen Startzustand ein Endzustand ist, akzeptiert mindestens das leere Wort.
===Sprachen vergleichen===
Gegeben sind über <math>\Sigma = \{K; E\}</math> die Sprache <math>L_Z = \{w \in \Sigma^* \mid |w| = 2\}</math> aller Wörter aus zwei Zeichen und die Sprache <math>L_E</math> aller Wörter mit mindestens einem <math>E</math> aus dem Beispiel [[#Unendliche Sprache in Mengenschreibweise angeben|Unendliche Sprache in Mengenschreibweise angeben]].
# '''Aufzählen:''' <math>L_Z</math> ist endlich und enthält <math>2^2 = 4</math> Wörter: <math>L_Z = \{KK; KE; EK; EE\}</math>.
# '''Schnittmenge:''' Zu beiden Sprachen gehören die Wörter aus zwei Zeichen, die ein <math>E</math> enthalten: <math>L_Z \cap L_E = \{KE; EK; EE\}</math>.
# '''Teilmenge prüfen:''' <math>L_Z \subseteq L_E</math> gilt nicht, denn <math>KK \in L_Z</math>, aber <math>KK \notin L_E</math>. Auch <math>L_E \subseteq L_Z</math> gilt nicht, denn <math>E \in L_E</math>, aber <math>E \notin L_Z</math>. Jeweils ein Gegenbeispiel genügt.
# '''Vereinigungsmenge:''' <math>L_Z \cup L_E</math> enthält alle Wörter, die zwei Zeichen lang sind oder ein <math>E</math> enthalten. Dazu gehören zum Beispiel <math>KK</math>, <math>E</math> und <math>KKE</math>, nicht aber <math>K</math> oder <math>KKK</math>.


[[Kategorie:Formale Sprachen]]
[[Kategorie:Formale Sprachen]]
[[Kategorie:AHR I Informatik LK]]
[[Kategorie:AHR I Informatik LK]]