Alphabet: Unterschied zwischen den Versionen
Keine Bearbeitungszusammenfassung |
Keine Bearbeitungszusammenfassung |
||
| 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_n\} \quad \text{mit } n \in \mathbb{N}, \, n \ge 1</math> | ||
Für ein Alphabet und seine Elemente gelten folgende Eigenschaften: | Für ein Alphabet und seine Elemente gelten folgende Eigenschaften: | ||
- '''Elemente (Zeichen / Buchstaben):''' Die einzelnen Elemente <math>a \in \Sigma</math> heißen '''Zeichen''', '''Symbole''' oder '''Buchstaben''' des Alphabets. Das können Buchstaben, Ziffern, Satzzeichen oder beliebige andere festgelegte Symbole sein. | |||
- '''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. | |||
==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>). | |||
- '''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>. | |||
- '''[[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. | |||
==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; 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; 1; 2; 3; 4; 5; 6; 7; 8; 9\}</math>:''' Umfasst die zehn Ziffern zur Darstellung von Dezimalzahlen, Postleitzahlen oder PIN-Codes. | |||
- '''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. | |||
Dabei ist streng zwischen einzelnen Zeichen des Alphabets (<math>\in \Sigma</math>) und zusammengesetzten Wörtern (<math>\in \Sigma^*</math>) zu unterscheiden: | Dabei ist streng zwischen einzelnen Zeichen des Alphabets (<math>\in \Sigma</math>) und zusammengesetzten Wörtern (<math>\in \Sigma^*</math>) zu unterscheiden: | ||
- <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>). | |||
===Eingabealphabet eines Kaffeeautomaten bestimmen=== | ===Eingabealphabet eines Kaffeeautomaten bestimmen=== | ||
| Zeile 33: | Zeile 33: | ||
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 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: | |||
:<math>\Sigma = \{K | :<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>. | |||
- '''Akzeptierte Sprache (<math>L \subseteq \Sigma^*</math>):''' Nur diejenigen Wörter aus <math>\Sigma^*</math>, die der [[Endlicher Automat|Automat]] akzeptiert (bei denen das Satzfach genau 4 Einheiten erreicht und der Endzustand <math>q_4</math> erreicht wird), 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]] | ||