Compilerbau: Formale Sprachen

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 w₁ und w₂
	Operatoren: +, ++, ⋅, nichts

ε	neutrales Element bezüglich Konkatenation
	w₁ ⋅ ε = w₁ ε ⋅ w₁ = w₁

(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}

L₀	{}
L₁	{ε}
L₂	{p \| p ∈ A^* ⋅ prim(p)}
L₃	{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)

Formale Sprachen