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 </math(<math>L\subset \sigma ^{*} $) heißt formale Sprache

Präfix

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