Alphabet: Unterschied zwischen den Versionen
Keine Bearbeitungszusammenfassung |
Keine Bearbeitungszusammenfassung |
||
| (Eine dazwischenliegende Version desselben Benutzers wird nicht angezeigt) | |||
| Zeile 5: | Zeile 5: | ||
Ein '''Alphabet''' <math>\Sigma</math> (griechischer Großbuchstabe Sigma) ist eine endliche, nicht leere [[Menge]] von [[Zeichen]] (Symbolen): | Ein '''Alphabet''' <math>\Sigma</math> (griechischer Großbuchstabe Sigma) ist eine endliche, nicht leere [[Menge]] von [[Zeichen]] (Symbolen): | ||
:<math>\Sigma = \{a_1 | :<math>\Sigma = \{a_1; a_2; \dots; a_m\} \quad \text{mit } m \in \mathbb{N} \text{ und } m \ge 1</math> | ||
Dabei ist <math>m</math> die Anzahl der Zeichen des Alphabets und <math>\mathbb{N}</math> die Menge der natürlichen Zahlen. | |||
Für ein Alphabet und seine Elemente gelten folgende Eigenschaften: | Für ein Alphabet und seine Elemente gelten folgende Eigenschaften: | ||
| Zeile 11: | Zeile 13: | ||
* '''Unteilbarkeit:''' Jedes Zeichen <math>a \in \Sigma</math> bildet innerhalb des Alphabets eine kleinste, nicht weiter zerlegbare Einheit. | * '''Unteilbarkeit:''' Jedes Zeichen <math>a \in \Sigma</math> bildet innerhalb des Alphabets eine kleinste, nicht weiter zerlegbare Einheit. | ||
* '''Endlichkeit und Nichtleerheit:''' Ein Alphabet muss mindestens ein Zeichen enthalten (<math>\Sigma \neq \emptyset</math>) und darf nur aus endlich vielen Zeichen bestehen. | * '''Endlichkeit und Nichtleerheit:''' Ein Alphabet muss mindestens ein Zeichen enthalten (<math>\Sigma \neq \emptyset</math>) und darf nur aus endlich vielen Zeichen bestehen. | ||
* '''Schreibweise:''' Wie bei jeder [[Menge]] stehen die Zeichen in Mengenklammern und werden durch ein Semikolon getrennt. Die Reihenfolge spielt keine Rolle, und jedes Zeichen wird nur einmal genannt. | |||
==Zusammenhang mit Wörtern und formalen Sprachen== | ==Zusammenhang mit Wörtern und formalen Sprachen== | ||
Aus den Zeichen eines Alphabets <math>\Sigma</math> werden schrittweise komplexere Strukturen der theoretischen Informatik aufgebaut: | Aus den Zeichen eines Alphabets <math>\Sigma</math> werden schrittweise komplexere Strukturen der theoretischen Informatik aufgebaut: | ||
* '''[[Wort]]:''' Eine endliche Folge von Zeichen aus <math>\Sigma</math> heißt Wort über dem Alphabet <math>\Sigma</math>. Auch das leere Wort <math>\varepsilon</math> (ohne jedes Zeichen) ist ein Wort über <math>\Sigma</math>, gehört selbst aber nicht als Zeichen zum Alphabet (<math>\varepsilon \notin \Sigma</math>). | * '''[[Wort]]:''' Eine endliche Folge von Zeichen aus <math>\Sigma</math> heißt Wort über dem Alphabet <math>\Sigma</math>. Auch das leere Wort <math>\varepsilon</math> (ohne jedes Zeichen) ist ein Wort über <math>\Sigma</math>, gehört selbst aber nicht als Zeichen zum Alphabet (<math>\varepsilon \notin \Sigma</math>). | ||
* '''Kleenesche Hülle <math>\Sigma^*</math>:''' Die Menge aller endlichen Wörter, die sich durch beliebiges Aneinanderhängen von Zeichen aus <math>\Sigma</math> bilden lassen (einschließlich des leeren Wortes <math>\varepsilon</math>), wird mit <math>\Sigma^*</math> bezeichnet. Ohne das leere Wort schreibt man <math>\Sigma^+ = \Sigma^* \setminus \{\varepsilon\}</math>. | * '''Kleenesche Hülle <math>\Sigma^*</math>:''' Die Menge aller endlichen Wörter, die sich durch beliebiges Aneinanderhängen von Zeichen aus <math>\Sigma</math> bilden lassen (einschließlich des leeren Wortes <math>\varepsilon</math>), wird mit <math>\Sigma^*</math> bezeichnet. Ohne das leere Wort schreibt man <math>\Sigma^+</math>. Als [[Menge#Differenzmenge|Differenzmenge]] geschrieben gilt <math>\Sigma^+ = \Sigma^* \setminus \{\varepsilon\}</math>. | ||
* '''[[Formale Sprache]]:''' Eine Teilmenge <math>L \subseteq \Sigma^*</math> zulässiger Wörter heißt formale Sprache über <math>\Sigma</math>. Bei einem [[Endlicher Automat|endlichen Automaten]] nennt man <math>\Sigma</math> das '''Eingabealphabet''', aus dessen Zeichen die Eingabewörter bestehen. | * '''[[Formale Sprache]]:''' Eine [[Menge#Teilmenge|Teilmenge]] <math>L \subseteq \Sigma^*</math> zulässiger Wörter heißt formale Sprache über <math>\Sigma</math>. Bei einem [[Endlicher Automat|endlichen Automaten]] nennt man <math>\Sigma</math> das '''Eingabealphabet''', aus dessen Zeichen die Eingabewörter bestehen. | ||
==Beispiele== | ==Beispiele== | ||
===Typische Alphabete in der Informatik angeben=== | ===Typische Alphabete in der Informatik angeben=== | ||
Je nach Anwendungsfall werden in der Informatik unterschiedliche Alphabete als Zeichenvorrat festgelegt: | Je nach Anwendungsfall werden in der Informatik unterschiedliche Alphabete als Zeichenvorrat festgelegt: | ||
* '''Binäralphabet <math>\Sigma_{\text{bool}} = \{0 | * '''Binäralphabet <math>\Sigma_{\text{bool}} = \{0; 1\}</math>:''' Enthält genau die beiden Bits <math>0</math> und <math>1</math>. Auf diesem Alphabet basieren sämtliche Maschinendaten, Binärzahlen und Speicherinhalte eines Computers. | ||
* '''Dezimalalphabet <math>\Sigma_{10} = \{0 | * '''Dezimalalphabet <math>\Sigma_{10} = \{0; 1; 2; 3; 4; 5; 6; 7; 8; 9\}</math>:''' Umfasst die zehn Ziffern zur Darstellung von Dezimalzahlen, Postleitzahlen oder Telefonnummern. | ||
* '''Lateinisches Kleinbuchstaben-Alphabet <math>\Sigma_{\text{lat}} = \{a | * '''Lateinisches Kleinbuchstaben-Alphabet <math>\Sigma_{\text{lat}} = \{a; b; c; \dots; x; y; z\}</math>:''' Besteht aus den 26 Kleinbuchstaben zur Bildung einfacher Textwörter. | ||
===Zeichen und Wörter unterscheiden=== | |||
Zwischen den einzelnen Zeichen eines Alphabets (<math>\in \Sigma</math>) und den daraus zusammengesetzten Wörtern (<math>\in \Sigma^*</math>) ist streng zu unterscheiden. Für das Dezimalalphabet <math>\Sigma_{10} = \{0; 1; 2; \dots; 9\}</math> gilt: | |||
* <math>0 \in \Sigma_{10}</math> und <math>1 \in \Sigma_{10}</math> sind einzelne Zeichen des Dezimalalphabets. | * <math>0 \in \Sigma_{10}</math> und <math>1 \in \Sigma_{10}</math> sind einzelne Zeichen des Dezimalalphabets. | ||
* <math>10 \notin \Sigma_{10}</math> ist '''kein''' einzelnes Zeichen des Alphabets, sondern ein aus zwei Zeichen zusammengesetztes [[Wort]] über <math>\Sigma_{10}</math> (<math>10 \in \Sigma_{10}^*</math>). | * <math>10 \notin \Sigma_{10}</math> ist '''kein''' einzelnes Zeichen des Alphabets, sondern ein aus zwei Zeichen zusammengesetztes [[Wort]] über <math>\Sigma_{10}</math> (<math>10 \in \Sigma_{10}^*</math>). | ||
* Der Buchstabe <math>A</math> gehört nicht zum Dezimalalphabet (<math>A \notin \Sigma_{10}</math>). Die Zeichenfolge <math>1A</math> ist deshalb kein Wort über <math>\Sigma_{10}</math> (<math>1A \notin \Sigma_{10}^*</math>). | |||
* Das leere Wort <math>\varepsilon</math> ist ein Wort über <math>\Sigma_{10}</math>, aber kein Zeichen: <math>\varepsilon \in \Sigma_{10}^*</math> und <math>\varepsilon \notin \Sigma_{10}</math>. | |||
===Eingabealphabet eines Kaffeeautomaten bestimmen=== | ===Eingabealphabet eines Kaffeeautomaten bestimmen=== | ||
[[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 besitzt zwei Auswahltasten: Kaffee (<math>K</math>, erzeugt 1 Einheit Kaffeesatz) und Espresso (<math>E</math>, erzeugt 2 Einheiten Kaffeesatz). Das Satzfach des Automaten ist bei genau 4 Einheiten voll. | Ein Kaffeeautomat besitzt zwei Auswahltasten: Kaffee (<math>K</math>, erzeugt 1 Einheit Kaffeesatz) und Espresso (<math>E</math>, erzeugt 2 Einheiten Kaffeesatz). Das Satzfach des Automaten, der Behälter für den Kaffeesatz, ist bei genau 4 Einheiten voll. | ||
* '''Eingabealphabet:''' Da der Automat ausschließlich die beiden Tastendrücke <math>K</math> und <math>E</math> als Eingabesymbole kennt, lautet das Eingabealphabet | * '''Eingabealphabet:''' Da der Automat ausschließlich die beiden Tastendrücke <math>K</math> und <math>E</math> als Eingabesymbole kennt, lautet das Eingabealphabet <math>\Sigma = \{K; E\}</math>. | ||
* '''Wörter über dem Alphabet (<math>\Sigma^*</math>):''' Durch Hintereinanderdrücken der Tasten entstehen [[Wort|Wörter]] über <math>\Sigma</math>, zum Beispiel <math>KK</math>, <math>KKKK</math>, <math>EE</math> oder <math>KEK</math>. | * '''Wörter über dem Alphabet (<math>\Sigma^*</math>):''' Durch Hintereinanderdrücken der Tasten entstehen [[Wort|Wörter]] über <math>\Sigma</math>, zum Beispiel <math>KK</math>, <math>KKKK</math>, <math>EE</math> oder <math>KEK</math>. | ||
* '''Akzeptierte Sprache (<math>L \subseteq \Sigma^*</math>):''' Nur diejenigen Wörter aus <math>\Sigma^*</math>, | * '''Akzeptierte Sprache (<math>L \subseteq \Sigma^*</math>):''' Nur diejenigen Wörter aus <math>\Sigma^*</math>, nach deren letztem Zeichen der [[Endlicher Automat|Automat]] im Endzustand <math>q_4</math> steht (das Satzfach ist dann mit genau 4 Einheiten voll), bilden seine [[Formale Sprache|Sprache]] <math>L</math>. Die Wörter <math>KKKK</math> (<math>1 + 1 + 1 + 1 = 4</math>) und <math>EE</math> (<math>2 + 2 = 4</math>) gehören zu <math>L</math>. Das Wort <math>KK</math> (<math>1 + 1 = 2</math>) ist zwar ein gültiges Wort über dem Alphabet <math>\Sigma</math> (<math>KK \in \Sigma^*</math>), gehört aber nicht zur akzeptierten Sprache (<math>KK \notin L</math>). | ||
[[Kategorie:Formale Sprachen]] | [[Kategorie:Formale Sprachen]] | ||
[[Kategorie:AHR I Informatik LK]] | [[Kategorie:AHR I Informatik LK]] | ||