Formale Sprachen

By | 10. Februar 2018

Eine formale Sprache ist eine abstrakte Sprache, bei der im Unterschied zu konkreten Sprachen oft nicht die Kommunikation im Vordergrund steht, sondern die mathematische Verwendung. Vor allem in der Informatik spielen formale Sprachen, zur Beschreibung von Softwaresystemen eine wichtige Rolle.

Der Aufbau einer formalen Sprache ist dem Aufbau einer natürlichen Sprache nicht unähnlich, hat aber eine Besonderheiten in der Darstellung:

Eine formale Sprache besteht aus einer bestimmten Menge von Zeichenketten, die aus einem Zeichenvorrat („Alphabet“, Grundsymbole) zusammengesetzt werden.

Ein Wort über (aus) einem Alphabet ist eine Hintereinanderreihung (Konkatenation) endlich vieler Symbole aus der Menge des Alphabets. Es gibt auch ein leeres Wort, das ist das Wort, das aus keinem Symbol besteht. Die Menge aller möglichen Wörter über ∑ wird als ∑* bezeichnet. Damit läßt sich eine etwas verfeinerte Definition einer formalen Sprache beschreiben:

Eine formale Sprache über einem Alphabet ∑,  ist eine bestimmte Teilmenge der Menge ∑* aller möglichen Wörter über ∑.

Beispielsweise ist das Alphabet zur Darstellung aller natürlichen Zahlen gegeben durch folgende Menge von Symbolen: ∑= {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}.

Nehmen wir als komplexeres Beispiel folgendes Alphabeth:

∑={I,V,X,L,C,D,M}

Die Menge aller Möglichen Wörter die mit Hilfe des Alphabets ∑ gebildet werden können bezeichnet man dann als ∑*.

Gemäß obiger Definition ist eine formale Sprache eine Teilmenge der Menge ∑*. In unserem Beispiel wäre damit die Menge L1, mit

L 1 = {I,II,III,    IV, V, VI, VII, VIII,    IX, X, XI, XII, XIII,   …,  L, C, D, M}

eine formale Sprache… und würde die Menge der römischen Zahlen beschreiben.

Die Menge L2, mit

L2 = {L, X, XL, XXL, XXXL}

entstammt aus dem selben Alphabet ∑ und beschreibt eine Sprache zur Beschreibung der T-Shirt Größen in unserer Zeit.

Grammatiken

Die eindeutige Beschreibung einer formale Sprache mit Hilfe von Regeln, die aus der Menge aller Möglichen Zeichen ∑* nur die gewünschten Zeichen spezifizieren, nennt man eine Grammatik. Eine Grammatik G wird durch eine 4-Tupel (N, T, S, P) beschreiben:

  • N ist die Menge aller Nichtterminalsymbole
  • T ist die Menge aller Terminalsymbole
  • S ist das Startsymbol, ist ein Element von N
  • P ist die Menge aller Regeln (auch Produktionen genannt)

Eine Grammatik erzeugt eine Sprache aus Wörtern die sich durch wiederholtes Anwenden der Regeln erzeugen (ableiten) lässt.

Beispiel

Die folgende Grammatik über dem Alphabet ∑= {+, 1, 2, 3} beschreibt eine Sprache mit der sich beliebig lange Summen der Ziffern 1, 2, 3 beschreiben lassen:

(R1) Summe –> Ziffer
(R2) Summe –> Summe + Ziffer
(R3) Ziffer –> 1
(R4) Ziffer –> 2
(R5) Ziffer –> 3

Das Startsymbol dieser Sprache ist Summe, Davon ausgehend kann man nun durch Anwenden der beschrieben Regeln Wörter der Sprache erzeugen. Beispielsweise würde sich der Ausdruck:

3+1+3+2+2

Durch folgende Ableitung beschreiben lassen:
(R1) (R5) (R2) (R3) (R2) (R5) (R2) (R4) (R2) (R4)

Reguläre Ausdrücke

Reguläre Ausdrücke beschreiben eine Familie von formalen Sprachen. Diese regulären Sprachen bilden die ausdrucksschwächsten Stufe der Chomsky-Hierarchie aller formalen Sprachen.

Ein regulärer Ausdruck besteht aus den Zeichen des zugrunde liegenden Alphabets ∑ in Kombination mit folgenden Metazeichen: [ ] { } ( ) | ? + – * ^$ \ . 

Der reguläre Ausdruck ab(bb)*a über dem  Alphabet ∑= {a, b}, erzeugt die Sprache die aus dem  Zeichen a und danach einer ungeraden Zahl an b’s, gefolgt von einem schließenden a besteht. Die Sprache ist demnach {aba, abbba, abbbbba…}.

Eine reguläre Sprache kann man statt durch einen regulären Ausdruck auch durch eine reguläre Grammatik beschreiben.

(R1)  S–>aA
(R2)  A–>bB
(R3)  B–>a
(R4)  B–>bC
(R5)  C–>bB

Die Sprache besteht damit  aus Wörtern der Art {aba, abbba, abbbbba…}, jedes Wort besteht wie oben schon beschrieben, aus einem a und danach einer ungeraden Zahl an b’s, gefolgt von einem schließenden a.

Weitere Beispiele regulärer Ausdrücke

Der reguläre Ausdruck

 (a|b|c ) (a|b|c ) (a|b|c )  

beschreibt die Sprache deren Wörter nur aus den 3 Buchstaben a,b,c bestehen. Also aus genau 27 Wörtern {aaa, aab, aac, aba, abb, usw.}

In den folgenden Beispielen wird die Rolle der o.g. Metazeichen verständlich, diese erlauben eine verkürzte Darstellung in dem sie Aufzählungen, Wiederholungen oder Alternativen vereinfachend beschreiben:

[0…9]     beschreibt eine Zahl von 0  bis 9

0,[0…9]*  beschreibt die Zahl o, mit beliebig vielen Nachkommastellen

P[a..z]*   beschreibt alle Wörter die mit dem Buchstaben P beginnen und dem beliebig viele Kleinbuchstaben folgen dürfen

A|P[a..z]*   beschreibt alle Wörter die mit dem Buchstaben A oder P beginnen und beliebig viele Kleinbuchstaben folgen dürfen

Bedeutung

Reguläre Ausdrücke haben in der Informatik ein breites Anwendungsspektrum. Beispielsweise zur Überprüfung von Eingaben oder zur Spezifikation von Suchmasken finden sich in praktisch allen Anwendungsfeldern reguläre Ausdrücke.

Beispielsweise bietet das Open-Office Paket die Möglichkeit mit Hilfe regulärer Ausdrücke Such-Bedingungen zu beschreiben. Dazu wird im Suchen-Dialog die Erweiterte Such-Funktion aufgeklappt und dort findet man die Möglichkeit reguläre Ausdrücke anzukreuzen. Dadurch kann man im Such-Feld dann reguläre Ausdrücke eingeben. Damit lassen sich dann beispielsweise korrekte Telephon-Nummern identifizieren.

Weitere Anwendungsmöglichkeiten findet man auch im Zusammenhang mit endlichen Automaten: http://profhof.com/endliche-automaten/