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