Beispiele formaler Sprachen

In diesem Kurs haben wir bereits verschiedene formale Sprachen kennengelernt. Diese sind u. a. die Relationenalgebra, die Datenbankabfragesprache SQL und die Programmiersprache Python:

Mithilfe der Relationenalgebra können Anfragen auf einem Datenbestand, der als Relationen gegeben ist formuliert werden. Die folgende Anfrage gibt alle Namen der Produkte zurück, die beim Großhändler oder im eigenen Shop gelistet sind:

π_Name(GProdukt) ∪ π_Name(SProdukt)

Hier sind die Symbole π für die Projektion oder die Vereinigung ∪ Teil der formalen Sprache der Relationenalgebra. Sie können nicht beliebig miteinander kombiniert werden, z. B. müssen auf π die Namen der Attribute folgen, die wir ausgeben möchten.

Hier sehen wir eine SQL Anweisung, die den Namen eines Attributs ändert:


    ALTER TABLE Schueler
    RENAME 'Klassenstufe' TO 'Klasse';

Die Schlüsselwörter ALTER, TABLE und TO sind Teil des Alphabets der Sprache SQL, jede Anweisung muss mit einem Semikolon ; abschließen.

Hier sehen wir ein Programm, geschrieben in Python:


    liste = [1, 3, 8]
    for l in liste:
        print(l)
    print('Ende')

Zu beachtende Syntaxregeln sind z. B. der Doppelpunkt : , der die Kopfzeile der Schleife abschließt oder die eckigen Klammern [ und ], die die Elemente der Liste umschließen

Die Römischen Zahlen als formale Sprache

Mit römische Zahlen können Zahlen mithilfe der lateinischen Buchstaben \(\text{I}, \text{V}, \text{X}, \text{L}, \text{C}, \text{D}\) und \(\text{M}\) Colosseum beschrieben werden. Es handelt sich dabei um eine Zahlschrift.

Wie könnte die Schreibweise der römische Zahlen als formale Sprache angegeben werden? Hierfür definieren wir unser Alphabet und die Menge der zulässigen Wörter über dem Alphabet, sie bilden die Sprache:

Alphabet: \( \Sigma = \{\text{I}, \text{V}, \text{X}, \text{L}, \text{C}, \text{D}, \text{M}\} \)
Menge aller Wörter \( w\) über dem Alphabet: \( \Sigma^* = \{\text{LXX}, \text{XXL}, \text{LILLI}, ...\} \)
Sprache der römischen Zahlen: \( \mathcal{L}=\{\text{I}, \text{II}, \text{III}, \text{IV}, \text{V}, \text{VI}, \text{VII}, \text{VIII}, \text{IX}, \text{X}, ...\} \)

Die Sprache \(\mathcal{L}\) der römischen Zahlen ist eine echte Teilmenge von \( \Sigma^* \), der Menge aller möglichen Wörter über \( \Sigma \).