Alphabet

Ein Alphabet ist eine endliche nicht leere Menge von Zeichen. Als normales Symbol für das Alphabet wird <math>\Sigma</math> verwendet. <math>\Sigma^*</math> umfasst alle Symbole sowie <math>\epsilon</math>, das leere Wort.

Eine Teilmenge von <math>\Sigma</math> (<math>L\subseteq\Sigma^*</math>) heißt formale Sprache

Präfix

Die Symbolfolge ab ist das Präfix des Elements abc, wenn <math>abc\in\Sigma^+</math> gilt.