Formale Sprachen – Die Basics

Formale Sprachen sind ein wesentlicher Bestandteil der theoretischen Informatik. Im Vergleich zu unserer Sprache, geht es bei formalen Sprachen, um die mathematische Verwendung. Durch einen gewissen Zeichenvorrat können mittels Verkettung beispielsweise Worte gebildet werden. Auch Programmiersprachen, wie C, stellen eine formale Sprache dar.

Um ein Verständnis für formale Sprachen zu entwickeln, sind deshalb ein paar grundlegende Definitionen wichtig. Die folgenden Begrifflichkeiten sind beinahe selbsterklärend und somit auch sehr leicht zu merken, denoch elementar, um ein Grundverständnis für formale Sprachen zu entwickeln.

Alphabet

Alphabet ist eine endliche nichtleere Menge. Die Elemente bezeichnet man als Zeichen.

Beispiel hierfür kann sein:

A₀ = {A, B, C, … , X, Y, Z}

A₁ = {Regen, Schnee, Sonne, Wind, Hagel, Wolken}

A₁ kann also auch ein Alphabet sein. Wichtig hierbei ist allerdings, das man sich die Elemente als Karteikarten vorstellt, da sie nicht ein einzelne Tastaturanschläge zerlegbar sind, sondern als Ganzes betrachtet werden. Diese Zeichen nennt man auch atomare Zeichen.

Wort

Eine Zeichenfolge w ist ein Wort über dem Alphabet A, wenn alle Zeichen von w in A enthalten sind. Auch eine leere Zeichenkette kann ein Wort darstellen. ε steht für das leere Wort „“.

Heißt also nichts anderes, als ich kann nur Wörter aus dem mir verfügbaren Zeichensatz bzw. Alphabet bilden. Klingt völlig verständlich.

„FRUEHLING“ „SOMMER“ „HERBST“ „WINTER“ wären also gültige Wörter über dem Alphabet A0.

Länge des Wortes

Die Länge eines Wortes wird, gleich dem Betrag in der Mathematik, als |w| notiert.

So hat hat Beispiel das Wort w = „Informatik“ eine Länge |w| = 10

Wortbildung

Um ein Wort zu bilden gibt es die einfache Operation der Verkettung oder Konkatenation. So ist es uns möglich aus dem Alphabet {a, b, c} das Wort „ab“ durch Verkettung der Zeichen a und b zu bilden. Die Verkettung als Operation wird oft als „a“ ∘ „b“ dargestellt.

Ebenso lassen sich durch Verkettung zweier Wörter eines Alphabets, wiederrum neue Wörter bilden:

„abend“ o „essen“ = „abendessen“

Wortmenge

Alle Wörter über dem Alphabet A bezeichnet man als Wortmenge. Das leere Wort ε ist Bestandteil jeder Wortmenge.

Sprache

Sofern die Sprache L eine Teilmenge von Alphabet A ist, bezeichnet man L als Sprache über Alphabet A. Eine Sprache ist also eine Wortmenge.

Zusammenfassung

Abschließend bleibt nicht viel zu sagen, außer nochmals zu betonen, dass die oberen Definition die Grundlagen für das weitere (Selbst)studium auf dem Gebiet der theoretischen Informatik bilden. Das leere Wort ε hat eine Länge |ε| = 0, worüber jetzt niemand wirklich überrascht sein wird. Bei der Verkettung mit dem leeren Wort entstehen keine neuen Wörter.

Im nächsten Teil geht es um die Formale Grammatik. Was darunter verstanden wird