Alphabet: Unterschied zwischen den Versionen

Keine Bearbeitungszusammenfassung
Keine Bearbeitungszusammenfassung
 
(4 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
== Einführung ==[[Datei:Antike Alphabete.png|mini]]
[[Datei:Antike Alphabete.png|mini|Verschiedene historische Alphabete]]
Ein Computer arbeitet im Prinzip mit Text, d.h. mit Folgen von Symbolen aus einem bestimmten Alphabet. Auch Grafiken werden letztendlich als Text gespeichert (z.B. HTML).  
Computer verarbeiten Texte, Programme und selbst Grafiken intern als Folgen einzelner Symbole. Ein Alphabet legt als fester Zeichenvorrat fest, welche Grundsymbole für die Bildung solcher Zeichenfolgen überhaupt erlaubt sind.


Ein Alphabet ist eine endliche nicht leere Menge ∑. Die Elemente eines Alphabets werden Buchstaben genannt. Die Buchstaben des Alphabets können alle möglichen Symbole (Ziffer, Zeichen,..) sein. Ein in der Informatik oft gebrauchtes Alphabet ist ∑bool ={0,1}.  Weitere Beispiele typischer Alphabete sind:
==Definition==
Ein '''Alphabet''' <math>\Sigma</math> (griechischer Großbuchstabe Sigma) ist eine endliche, nicht leere [[Menge]] von [[Zeichen]] (Symbolen):


* ∑bool={0,1}Alphabet der Binärzahlen
:<math>\Sigma = \{a_1; a_2; \dots; a_m\} \quad \text{mit } m \in \mathbb{N} \text{ und } m \ge 1</math>
* ∑10={0,1,2,3,4,5,6,8,9} Alphabet der Dezimalzahlen
* ∑lat ={a,b,c,d,e,f,g,h,...,x,y,z} Lateinisches Alphabet


Ein [[Wort]] über einem Alphabet Σ ist eine endliche Folge von Zeichen aus Σ.
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:
* '''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.
* '''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.


== Beispiel ==
==Zusammenhang mit Wörtern und formalen Sprachen==
[[Datei:DEA Kaffeeautomat.jpg|mini]]
Aus den Zeichen eines Alphabets <math>\Sigma</math> werden schrittweise komplexere Strukturen der theoretischen Informatik aufgebaut:
Für den folgenden Kaffeeautomaten besteht das Eingabealphabet aus den Zeichen/Buchstaben E und K. Aus E und K können Wörter gebildet werden (z.B. {KKKK} oder {EE}. Die Menge aller möglichen [[Wort|Wörter]] definiert die Sprache, die vom [[Automat|Automaten]] verstanden wird.
* '''[[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^+</math>. Als [[Menge#Differenzmenge|Differenzmenge]] geschrieben gilt <math>\Sigma^+ = \Sigma^* \setminus \{\varepsilon\}</math>.
* '''[[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==
===Typische Alphabete in der Informatik angeben===
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 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.
 
===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>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===
[[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, 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 <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>, 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:AHR I Informatik LK]]