Formale Sprachen

Neben deiner Muttersprache kennst du sicher noch weitere Sprachen: Fremdsprachen (Englisch, Französisch, Spanisch …), Zahlen oder die Formelsprache der Mathematik. Auch in der Informatik gibt es Sprachen: Programmiersprachen (Python, Java, C, …) oder Auszeichnunssprachen (HTML, Latex, Markdown). Deshalb beschäftigt sich auch die Theoretische Informatik mit diesem Thema.

Alphabet

Ein Alphabet ist eine endliche, nicht leere Menge von Zeichen.

Beispiele:

Wort

Ein Wort über demAlphabet ist eine Zeichenkette, die ausschließlich aus Zeichen aus besteht. Das leere Wort ist ein Wort in jedem beliebigen Alphabet.

Die Länge eines Wortes kurz , ist bestimmt durch die Anzahl aller Zeichen, die das Wort enthält. Mehrfachvorkommen werden mehrfach gezählt. Für das leere Wort gilt