Zeichen
Symbol
|
elementare Einheit
|
|
|
Alphabet A
|
eine endliche, nichtleere Menge von Zeichen
|
|
|
Zeichenkette
Zeichenfolge
Wort
|
endlich lange Folge von Zeichen über einem Alphabet
|
|
|
ε
|
die leere Zeichenfolge
|
|
|
A*
|
die Menge aller Wörter über einem Alphabet
|
|
|
?
|
Wieviele Wörter gibt es?
|
|
|
|w|
|
Länge eines Wortes
|
|
|ε| = 0
|
|---|
|
|
Präfix
|
eines Wortes w
|
|
beliebige Anzahl führender Zeichen von w
|
|---|
|
|
?
|
Wieviele Präfixe besitzt ein Wort der Länge n?
|
Suffix
|
eines Wortes w
|
|
beliebige Anzahl Zeichen am Ende von w
|
|---|
|
|
?
|
Wieviele Suffixe besitzt ein Wort der Länge n?
|
Konkatenation
|
zweier Wörter w1 und w2
|
|
Operatoren: +, ++, ⋅, nichts
|
|---|
|
|
ε
|
neutrales Element bezüglich Konkatenation
|
|
w1 ⋅ ε = w1
ε ⋅ w1 = w1
|
|---|
|
|
(A*, ⋅, ε)
|
bilden einen nicht kommutativen Monoid.
|
|
|
?
|
Was ist ein Monoid?
|
?
|
Was ist eine Halbgruppe?
|
Sprache L
|
über einem Alphabet A
|
|
L ⊆ A*
|
|---|
|
|
Beispiel
|
A = {0, 1, ..., 9}
|
|
|
L0 |
{}
|
L1 |
{ε}
|
L2 |
{p | p ∈ A* ⋅ prim(p)}
|
L3 |
{p | p ∈ A* ⋅ |p| ≤ 5}
|
?
|
Welche Sprachen sind endliche Sprachen?
|
|
|
Techniken |
zur Definition von formalen Sprachen
|
|
explizite Aufzählung
|
|
Mengendefinition
|
|
Automaten
|
|
Grammatiken
|
?
|
Welche Definitionen sind geeignet für unendliche Sprachen?
|
Parsen |
einer Zeichenfolge w:
|
|
w ∈ L(A)
|
|---|
Compilerbau & Formale Sprachen: Formale Sprachen
