Alphabet

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

Eine Teilmenge von $ \Sigma $ ($ L\subseteq \Sigma ^{*} $) heißt formale Sprache

Präfix

Die Symbolfolge ab ist das Präfix des Elements abc, wenn $ abc\in \Sigma ^{+} $ gilt.