Formale Sprachen
Alphabet: geordneter Zeichenvorrat
Formale Sprache: Menge von Zeichenketten, die aus den Symbolen eines beliebigen Alphabets aufgebaut sind.
Zeichenkette: endliche Folge von Symbolen, die ohne Zwischenraum hintereinander geschrieben werden (Verkettung)
Definition der zulässigen Zeichenketten einer Sprache durch induktive Definition
1. definitorische Anfangsbestimmung
2. generierende Bestimmung