Ins Open-Document-Format exportieren

Aufbau einer formalen Sprache

Um die Wörter einer Sprache festzulegen, müssen diese entweder alle aufgezählt werden oder durch ein Regelwerk zur Bildung (Syntax) beschrieben werden. Insbesondere wenn es unendlich viele Wörter gibt, ist eine Auflistung nicht möglich.
Beispiel: Um die Räume in einem Gebäude zu beschreiben werden Raumbezeichnungen verwendet. Dabei beschreibt ein Buchstabe die Ebene und die folgende Zahl die Raumnummer innhalb der Ebene. Als Alphabet für ein dreistöckiges Gebäude eignet sich folgendes Alphabet Σ={A, B, C, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Eine Raumbezeichnung ist korrekt, wenn sie mit einem Buchstaben beginnt und darauf eine dreiziffrige Zahl folgt, die auch führende Nullen haben darf. Gültige Raumbezeichnungen sind also z. B.: A001, B123, C012. Nicht zulässige Wörter wären AB01, 1231 oder 343A.

Produktionsregeln

Eine Sprache kann auch mit Hilfe von sogenannten Produktionsregeln gebildet werden. Eine Produktion besteh dabei aus zwei Teilen: Auf der linken Seite steht eine syntaktische Variable. Der anschließende Pfeil → zeigt an, dass diese Variable durch einen folgenden Ausdruck ersetzt werden kann. Dieser Ausdruck (Term) kann eine Folge von weiteren syntaktischen Variablen und Elementen des Alphabets sein.
Die Raumbezeichnungen von oben können mit folgenden Regeln gebildet werden:

(1) <Raumbezeichnung> → <Buchstabe><Ziffer><Ziffer><Ziffer>
(2) <Buchstabe> → A
(3) <Buchstabe> → B
(4) <Buchstabe> → C
(5) <Ziffer> → 0
(6) <Ziffer> → 1
(7) <Ziffer> → 2
(8) <Ziffer> → 3
(9) <Ziffer> → 4
(10) <Ziffer> → 5
(11) <Ziffer> → 6
(12) <Ziffer> → 7
(13) <Ziffer> → 8
(14) <Ziffer> → 9

Für die Erzeugung eines Wortes beginnt man mit der ersten Regel, also mit der Variablen <Raumbezeichnung>. Diese Variable heißt auch Startvariable.

Ableitung

Um zu überprüfen, ob ein Wort zu einer bestimmten Sprache gehört, muss man überprüfen, ob es eine Folge von Regeln gibt, durch deren Anwendung das Wort erzeugt werden kann. Diese Folge von Regeln nennt man auch Ableitung des Wortes. Das Wort A021 kann durch wie folgt abgeleitet werden:

RegelFortschritt der Ableitung
(1)<Raumbezeichnung>→<Buchstabe><Ziffer><Ziffer><Ziffer>
(2)<Raumbezeichnung>→A<Ziffer><Ziffer><Ziffer>
(5)<Raumbezeichnung>→A0<Ziffer><Ziffer>
(7)<Raumbezeichnung>→A02<Ziffer>
(6)<Raumbezeichnung>→A021

Terminale und Nichtterminale

Bei der Ableitung eines Wortes werden nach und nach alle syntaktischen Variablen durch Elemente des Alphabets ersetzt. Alle Zeichen des Alphabets nennt man deshalb Terminale. Alle syntaktischen Variablen heißen Nichtterminale. Ihre Menge wird häufig mit V bezeichnet.

Zusammenfassung von Regeln

Bei den obigen Produktionsregeln fällt auf, dass auf der linken Seite der Regeln immer wieder die gleichen syntaktischen Variablen auftauchen. Regeln mit gleicher linker Seite lassen sich zusammenfassen, indem man die möglichen verschiedenen Ersetzungen (rechte Seite der Regel) durch einen senkrechten Strich | trennt. Die Regeln (2), (3) und (4) können ersetzt werden durch
<Buchstabe> → A|B|C
Ebenso ergibt sich aus den Regeln (5) bis (14):
<Ziffer> → 0|1|2|3|4|5|6|7|8|9

Ableitungsbaum

Die Ableitung eines Wortes kann auch durch einen Ableitungsbaum dargestellt werden. An der Wurzel des Baumes steht die Startvariable. Jeder Ast kennzeichnet die Anwendung einer Produktionsregel. An den Blättern des Baumes befinden sich ausschließlich Terminale. Umgekehrt können Nichtterminale nicht Blätter des Ableitungsbaumes sein.

Grammatik einer formalen Sprache

Eine formale Sprache kann durch folgende vier Punkte eindeutig festgelegt werden:

  • das Alphabet Σ, also die Menge der Terminale
  • die Menge der syntaktischen Variablen (Menge der Nichtterminale)
  • die Menge der Produktionen, bezeichnet mit P
  • die Startvariable S, das heißt die syntaktische Variable, die immer zuerst ersetzt wird.

Zu beachten ist, dass die Terminale und Nichtterminale kein gemeinsames Element besitzen dürfen. Diese vier Mengen bilden zusammen die formale Grammatik G der Sprache. Man schreibt G=(V,Σ,P,S) (G ist eine Vierertupel, bestehend aus Nichtterminalen, Terminalen, den Produktionen und dem Startsymbol).

Zusammenfassung

  • Zur exakten Beschreibung einer formalen Sprache benötigt man eine Grammatik G=(V,Σ,P,S), die aus der Menge der syntaktischen Variablen V, dem Alphabet Σ, der Produktionsregeln P und dem Startsymbol Sbesteht.
  • Die Ableitung eines Wortes gibt an, wie ein Wort durch sukzessive Anwendung von Produktionsregeln gebildet werden kann. Die Ableitung eines Wortes ist meist nicht eindeutig.
  • Ein Ableitungsbaum ist eine graphische Darstellung der Ableitung eines Wortes als Baum. Die Blätter des Ableitungsbaumes bilden von links nach rechts die Folge der Zeichen des Wortes.
Cookies helfen bei der Bereitstellung von Inhalten. Durch die Nutzung dieser Seiten erklären Sie sich damit einverstanden, dass Cookies auf Ihrem Rechner gespeichert werden. Weitere Information
Drucken/exportieren