Home -> Themen -> Regelsprachen


Turing-Werkstatt

Theoretische Informatik am PC


O.Pletsch 1862

Download aller Beispiele
zur Simulation mit Turing-Werkstatt.exe

Formale Sprachen
Eine formale Sprache besteht aus einer Menge L von Worten, die aus den Zeichen einer vorgegebenen Menge T von Symbolen gebildet sind.

Beispiele :

  1. Die Menge L der natürlichen Zahlen, geschrieben in Dualdarstellung.
    0, 1, 10, 11, 100, 101, ......    T = { 0, 1 }
  2. Die Menge L der natürlichen Zahlen, geschrieben in unärer Darstellung.
    I, II, III, IIII, IIIII, ......    T= { I }
  3. Die Menge L aller Palindrome über T = { a, b }, das sind Worte, die sich nicht ändern, wenn man sie rückwärts liest.
    a, b, aa, bb, aaa, aba, bab, bbb, aaaa, abba, .....

Regelsprachen / Regelgrammatik
Regelsprachen sind formale Sprachen, die durch eine Regelgrammatik G festgelegt werden können. G ist ein Instrument um Wortmengen zu erzeugen und beschreibt den Aufbau der Worte, die zu einer Sprache gehören.

Grammatiken zu den Beispielen 1 - 3

  1. Eine Zahl Z ist die 0 oder sie beginnt mit einer 1 gefolgt von einer Ziffernfolge F.
    Z  ->  0 ;   Z  ->  1F ;
    Die Ziffernfolge F kann leer sein oder mit einer 0 bzw. 1 beginnen.
      F  ->  0F ;  F  ->  1F ;  F  -> _   ( _ das leere Wort )
    Z, F werden syntaktische Variable oder Nicht-Terminalsymbole genannt. N = {Z,F} ist die Menge der Nicht-Terminalsymbole. Die Symbole von A heißen Terminalsymbole.
    Ausgehend von dem Startsymbol Z kann man durch Anwendung der Ersetzungsregeln (Produktionen) jede natürliche Zahl erzeugen.
    Eine Ersetzungsregel  hat die Form :  Wort 1 -> Wort 2, d.h. Wort1 kann durch Wort2 ersetzt werden. Beide Worte können aus Terminal- und Nichtterminalzeichen gebildet werden. Allerdings muss Wort1 mindestens ein Nicht-Terminalzeichen enthalten. 
    Erzeugung (Ableitung) der Zahl 101 :
         Z -> 1F -> 10F -> 101F -> 101_ = 101
    Man startet mit dem Startsymbol Z und wendet nacheinander Ersetzungsregeln an bis man ein Wort erhalten hat, das nur aus Terminalsymbolen besteht. Alle Worte, die man aus dem Startsymbol so erhalten kann, bilden die durch G erzeugte Sprache L(G).
  2. Terminalsymbole T = { I }
    Nichtterminalsymbole { Z, F }, Startsymbol Z
    Produktionen  Z -> IF ;  F -> IF;  F -> _
    L(G) die Menge der natürlichen Zahlen in unärer Darstellung (Strichzahlen)
  3. Terminalsymbole T = { a, b } ; 
    Nichtterminalsymbole { P }, Startsymbol P
    Produktionen P -> a ; P -> b ; P -> _ ;  P -> aPa ; P -> bPb
  4. Ein weiteres Beispiel :
    Terminalsymbole T = { a, b, c }
    Nichtterminalsymbole { S, A, B }, Startsymbol S
    Produktionen  S -> ABSc ;  Ba -> aB;  Bc -> bc;   Bb -> bb; S -> _
    L(G) = { anbncn}

Regelsprachen sind aufzählbar
Begründung :
Man beginnt in Stufe 0 mit dem Startsymbol und bestimmt in Stufe 1 alle Worte, die sich aus dem Startsymbol durch Anwendung einer Ersetzungsregel erzeugen lassen. Aus diesen werden alle Worte ausgesondert und ausgegeben, die nur aus Terminalsymbolen bestehen. Die verbliebenen Worte von Stufe 1 haben alle mindestens ein Nichtterminalsymbol. Auf diese Worte werden nun nacheinander alle Ersetzungsregeln ausprobiert. Die dadurch erzielten Ergebnisse bilden die Worte von Stufe 2. Wiederum werden alle Wörter, die nur aus Terminalsymbolen bestehen, ausgesondert und ausgegeben. Solange noch Worte mit Nichtterminalsymbolen übrig bleiben wird der Prozess fortgesetzt.
Diese Vorgehensweise ist in der Maschine L(G).tm realisiert.

L(G).tm
ist eine TM mit drei Bändern, die L(G) aufzählt bei Eingabe der Ableitungsregeln und der Terminalsymbole einer Grammatik G.
Band 1 :
soll beim Start alle Terminalsymbole hintereinander enthalten, gefolgt von einem Leerzeichen und den Ersetzungsregeln von G, die hintereinander geschrieben werden, eingefasst von Kommata. Das Kommazeichen darf in G nicht vorkommen. Die erste Regel sollte mit dem Startsymbol beginnen. Beim Start sollte der S/L-Kopf auf dem Kommazeichen vor der ersten Regel stehen.
Band 2 
bleibt leer oder enthält ein Wort als Anfangswort für den Ableitungsprozess mit Start auf dem linken Rand.
Band 3 
bleibt leer.
Für G1 zur Beschreibung der natürlichen Zahlen ergibt sich folgende Anfangskonfiguration :

Anfangskonfiguration für G1
Der Buchstabe e in der Regel F -> e steht für das leere Wort bzw. das Löschen von F. Sollte die benutzte Grammatik ein e als Terminalsymbol benutzen, so muss es durch ein anderes Symbol ersetzt werden.
L(G).tm holt sich das Startsymbol aus der ersten Ersetzungsregel nach Band 2 und versucht dann alle Regeln auf das Startsymbol anzuwenden. Alle so erzeugten Worte werden nach Band 3 geschrieben. Diese Zwischenergebnisse werden dann geprüft, ob sie nur aus Terminalsymbolen bestehen, d.h. zu L(G) gehören. Ist das der Fall, so werden sie auf Band1 nach links ausgegeben. Zwischenergebnisse mit Nichtterminalsymbole werden nach Band 2 geschrieben und die Maschine versucht nun die Regeln auf diese Worte anzuwenden.

Hinweis
L(G).tm ist durch die Verwendung von Joker-Zeichen so allgemein formuliert, dass G beliebige Symbole als Terminal- und Nichtterminalsymbole enthalten kann. Sie ist daher ideal geeignet um den Ableitungsprozess von beliebigen Grammatiken zu visualisieren.
Will man nicht mit dem Startsymbol beginnen, sondern mit einem bereits erreichten Zwischenergebnis w starten, so schreibt man vor dem Start von L(G).tm das Wort w auf Band 2 und setzt den S/L-Kopf auf den linken Rand von w.

Übung
Laden Sie L(G).tm in Turing-Werkstatt.exe und ändern Sie die Eingabe so ab, dass L(G2) bis L(G4) aufgezählt werden.

Ein Akzeptor für L(G)
L(G)-Akzeptor.tm ist eine Turing-Maschine mit drei Bändern, die bei Eingabe der Ableitungsregeln einer Grammatik G und eines Wortes w prüft, ob w in L(G) liegt. Sie ist durch wenige Änderungen aus L(G).tm entstanden
Die Bandbelegung vor dem Start ist wie bei L(G).tm, mit dem Unterschied, dass statt der Elemente von T das zu untersuchende Wort w auf Band1 eingegeben werden muss. Die Maschine erzeugt wie L(G).tm alle vom Startsymbol abgeleiteten Worte und vergleicht diese mit w. Ist ein solcher Vergleich erfolgreich, so hält die Maschine mit positivem Resultat. Ist w nicht in L(G), so kann die Maschine in eine Endlosschleife übergehen.


Beim Laden von L(G)-Akzeptor.tm finden Sie bereits die Eingaben für G1 vor zur Erzeugung der natürlichen Zahlen. Als zu prüfendes Wort ist 1010011 eingegeben.
Anfangskonfiguration :

Anfangskonfiguration für G1
Der Buchstabe e in der Regel F -> e steht für das leere Wort bzw. das Löschen von F. Sollte die benutzte Grammatik ein e als Terminalsymbol benutzen, so muss es durch ein anderes Symbol ersetzt werden.

Testen Sie die Maschine mit anderen Worten bzw. mit anderen Grammatiken.


Letzte Änderung : 23.9.2016