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, a_2, \dots, a_n\} \quad \text{mit } n \in \mathbb{N}, \, n \ge 1</math>
:<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.
- '''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.
- '''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.


==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^+ = \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 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.
- '''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.
- '''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.
- '''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>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>).


===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:
- '''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>
:<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>, 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>).
- '''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]]