Zum Inhalt springen

Alphabet: Unterschied zwischen den Versionen

Aus FLBK-Wiki
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]]

Version vom 10. November 2026, 09:22 Uhr

Verschiedene historische Alphabete

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.

Definition

Ein Alphabet [math]\displaystyle{ \Sigma }[/math] (griechischer Großbuchstabe Sigma) ist eine endliche, nicht leere Menge von Zeichen (Symbolen):

[math]\displaystyle{ \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: - Elemente (Zeichen / Buchstaben): Die einzelnen Elemente [math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ \Sigma \neq \emptyset }[/math]) und darf nur aus endlich vielen Zeichen bestehen.

Zusammenhang mit Wörtern und formalen Sprachen

Aus den Zeichen eines Alphabets [math]\displaystyle{ \Sigma }[/math] werden schrittweise komplexere Strukturen der theoretischen Informatik aufgebaut: - Wort: Eine endliche Folge von Zeichen aus [math]\displaystyle{ \Sigma }[/math] heißt Wort über dem Alphabet [math]\displaystyle{ \Sigma }[/math]. Auch das leere Wort [math]\displaystyle{ \varepsilon }[/math] (ohne jedes Zeichen) ist ein Wort über [math]\displaystyle{ \Sigma }[/math], gehört selbst aber nicht als Zeichen zum Alphabet ([math]\displaystyle{ \varepsilon \notin \Sigma }[/math]). - Kleenesche Hülle [math]\displaystyle{ \Sigma^* }[/math]: Die Menge aller endlichen Wörter, die sich durch beliebiges Aneinanderhängen von Zeichen aus [math]\displaystyle{ \Sigma }[/math] bilden lassen (einschließlich des leeren Wortes [math]\displaystyle{ \varepsilon }[/math]), wird mit [math]\displaystyle{ \Sigma^* }[/math] bezeichnet. Ohne das leere Wort schreibt man [math]\displaystyle{ \Sigma^+ = \Sigma^* \setminus \{\varepsilon\} }[/math]. - Formale Sprache: Eine Teilmenge [math]\displaystyle{ L \subseteq \Sigma^* }[/math] zulässiger Wörter heißt formale Sprache über [math]\displaystyle{ \Sigma }[/math]. Bei einem endlichen Automaten nennt man [math]\displaystyle{ \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]\displaystyle{ \Sigma_{\text{bool}} = \{0; 1\} }[/math]: Enthält genau die beiden Bits [math]\displaystyle{ 0 }[/math] und [math]\displaystyle{ 1 }[/math]. Auf diesem Alphabet basieren sämtliche Maschinendaten, Binärzahlen und Speicherinhalte eines Computers. - Dezimalalphabet [math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ \in \Sigma }[/math]) und zusammengesetzten Wörtern ([math]\displaystyle{ \in \Sigma^* }[/math]) zu unterscheiden: - [math]\displaystyle{ 0 \in \Sigma_{10} }[/math] und [math]\displaystyle{ 1 \in \Sigma_{10} }[/math] sind einzelne Zeichen des Dezimalalphabets. - [math]\displaystyle{ 10 \notin \Sigma_{10} }[/math] ist kein einzelnes Zeichen des Alphabets, sondern ein aus zwei Zeichen zusammengesetztes Wort über [math]\displaystyle{ \Sigma_{10} }[/math] ([math]\displaystyle{ 10 \in \Sigma_{10}^* }[/math]).

Eingabealphabet eines Kaffeeautomaten bestimmen

Vollständiger DEA des Kaffeeautomaten

Ein Kaffeeautomat besitzt zwei Auswahltasten: Kaffee ([math]\displaystyle{ K }[/math], erzeugt 1 Einheit Kaffeesatz) und Espresso ([math]\displaystyle{ 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]\displaystyle{ K }[/math] und [math]\displaystyle{ E }[/math] als Eingabesymbole kennt, lautet das Eingabealphabet:

[math]\displaystyle{ \Sigma = \{K; E\} }[/math]

- Wörter über dem Alphabet ([math]\displaystyle{ \Sigma^* }[/math]): Durch Hintereinanderdrücken der Tasten entstehen Wörter über [math]\displaystyle{ \Sigma }[/math], zum Beispiel [math]\displaystyle{ KK }[/math], [math]\displaystyle{ KKKK }[/math], [math]\displaystyle{ EE }[/math] oder [math]\displaystyle{ KEK }[/math]. - Akzeptierte Sprache ([math]\displaystyle{ L \subseteq \Sigma^* }[/math]): Nur diejenigen Wörter aus [math]\displaystyle{ \Sigma^* }[/math], die der Automat akzeptiert (bei denen das Satzfach genau 4 Einheiten erreicht und der Endzustand [math]\displaystyle{ q_4 }[/math] erreicht wird), bilden seine Sprache [math]\displaystyle{ L }[/math]. Die Wörter [math]\displaystyle{ KKKK }[/math] ([math]\displaystyle{ 1+1+1+1=4 }[/math]) und [math]\displaystyle{ EE }[/math] ([math]\displaystyle{ 2+2=4 }[/math]) gehören zu [math]\displaystyle{ L }[/math]. Das Wort [math]\displaystyle{ KK }[/math] ([math]\displaystyle{ 1+1=2 }[/math]) ist zwar ein gültiges Wort über dem Alphabet [math]\displaystyle{ \Sigma }[/math] ([math]\displaystyle{ KK \in \Sigma^* }[/math]), gehört aber nicht zur akzeptierten Sprache ([math]\displaystyle{ KK \notin L }[/math]).