Formale Sprachen in JSLIM

Reguläre Sprachen

Primitiver Ansatz, L = abcd

Die Sprache L beschreibt nur ein einziges Wort, nämlich die Folge der Segmente a, b, c und d. Diese Sprache hat keinen praktischen Nutzen, wird an dieser Stelle aber benutzt, um zu illustrieren, wie Sequenzen unter Verwendung von Regeln bearbeitet werden können.

Idee. Man benötigt drei Regeln R1, R2 und R3, welche jeweils b, c und d einlesen. R1 wird in das Regelpaket des Startzustands geschrieben, wodurch der Vorgang des Parsens von nun an mit R1 beginnt. Die Regel R1 stellt sicher, dass a zu Beginn eingelesen wird. Das Regelpaket von R1 enthält nur die Regel R2, das von R2 nur R3. Das Regelpaket von R3 bleibt leer, wodurch das Parsen nach der Ausführung von R3 beendet wird.

Algorithmus. Oben beschriebene Idee lässt sich als einfacher Algorithmus darstellen.

• [STS] Beginne mit Segment a und Regel R1.
• [R1 ] Akzeptiere nur Segment b als nächstes Segment. Fahre mit Regel R2 fort.
• [R2 ] Akzeptiere nur Segment c als nächstes Segment. Fahre mit Regel R3 fort.
• [R3 ] Akzeptiere nur Segment d als nächstes Segment. Beende die Ableitung.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R3 beendet wurde.

Skizze. Die Ableitung des Eingabewortes abcd kann veranschaulicht werden, indem für jeden Ableitungsschritt die jeweilige Regelanwendung und die jeweiligen Änderungen der Kategorie aufgezeigt werden. Der Punkt wird an dieser Stelle benutzt, um die aktuelle Position innerhalb der Eingabefolge zu markieren. Zu beachten ist, dass die Kombination mit dem zweiten Segment beginnt. In komplexeren Grammmatiken kann zudem mehr als nur eine möglich Fortsetzung auftreten.

 a.bcd  R1: (a)(b) => (a) {R2}
 ab.cd  R2: (a)(c) => (a) {R3}
 abc.d  R3: (a)(d) => (a)   

Im ersten Ableitungsschritt kombiniert der Parser das erste mit dem zweiten Segment. Somit entspricht die Kategoriesequenz des ersten Segments der Kategoriesequenz des ursprünglichen Satzanfangs. Der aktuelle Ableitungsschritt wird mit einem Punkt angegeben, der immer dem kombinierten nächsten Segment vorausgeht.

Deklarative Spezifikation. An dieser Stelle ist die deklarative Spezifikation identisch mit der Ableitung. Dieser Umstand wird sich für Sprachen, die mehr als ein Wort beschreiben, ändern. In den folgenden Kapiteln werden Variablen verwendet, um Regeln allgemeiner und rekursiv anwendbar zu formulieren.

LX = {[a (a)], [b (b)], [c (c)], [d (d)]}
ST_S ={([(a)] {r_1})}
r_1: (a)(b) => (a) {r_2}
r_2: (a)(c) => (a) {r_3}
r_3: (a)(d) => (a) {}
ST_F ={([(a)] rp_{r_3})}

Da die deklarative Spezifikation nur geringfügig von der Implementation in JSLIM abweicht, wird diese in den weiteren Beispielen nicht weiter aufgeführt.

Code. Für den simplen Algorithmus dieser Grammatik reicht es aus, die Lexikonelemente auf irgendeine Weise unterscheidbar zu machen. Der einfachste Weg besteht darin, jede Oberfläche mit einer Kategorie zu versehen, die die Oberfläche widerspiegelt:

 [sur:a, cat:(a)], [sur:b, cat:(b)], [sur:c, cat:(c)], [sur:d, cat:(d)]  

Da JSLIM sich Merkmalsstrukturen und einer Reihe primitiver Operationen bedient, um die Änderungen des Satzanfangs zu realisieren, müssen die Regeln entsprechend angepasst werden.

 ST_S = {([cat: (a)], {R1})}
 
 R1 {R2} [cat: (a)] [cat: (b)] concat(NW.sur SS.sur)
 R2 {R3} [cat: (a)] [cat: (c)] concat(NW.sur SS.sur)
 R3    [cat: (a)] [cat: (d)] concat(NW.sur SS.sur)
 
 ST_F = {([cat: (a)] rp_R3)}

Komplexität. LAG: C1 (linear). Die Grammatik weist keine Ambiguitäten auf, da die Regelpakete maximal eine Regel referenzieren. PSG: regulär (linear). Die Sprache ist problemlos mittels regulärer Ausdrücke beschreibbar.

Kategorialer Ansatz, L = abcd

Die Anzahl an Regeln der Grammatik wird auf eine einzige beschränkt. Die Entscheidung, welches Zeichen zu welchem Zeitpunkt eingelesen werden darf, wird nun aufgrund der Kategorie des aktuellen Zwischenergebnisses des Parse-Vorgangs getroffen.

Idee. Nachdem das erste Wort a eingelesen wurde, legt dessen Kategorie fest, dass die Wörter b, c und d in exakt dieser Reihenfolge erwartet werden. Dies wird dadurch realisiert, dass die kategorialen Symbole der Wörter b, c und d in die Kategorie von a eingetragen werden. Nachdem b eingelesen wurde, wird das entsprechende Symbol aus der Kategorie a gelöscht und demensprechend als nächste Wörter c und d erwartet. Folgt c, so wird dieses wiederum aus der Kategorie gelöscht. Genauso wird mit d verfahren.

Algorithmus. Im Gegensatz zu vorher beschriebener Grammatik ist es in diesem Fall nötig, dass die Regeln einige einfache Operationen ausführen.

• [STS] Beginne mit dem Segment a und Regel R1.
• [R1] Stelle sicher, dass der Kategoriewert des nächsten Segments mit dem Wert identisch ist, der in der Kategoriesequenz des Satzanfangs ganz links steht. Entferne den Wert am linken Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R1 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R1 beendet wurde und die Kategorie des Satzanfangs leer ist.

Skizze. Sei w=abcd ∈ L. Die Regel R1 muss insgesamt drei Mal angewandt werden.

 a.bcd  R1:  (b c d)(b) => (c d) {R1}         
 ab.cd  R1:    (c d)(c) => (d)   {R1}         
 abc.d  R1:      (d)(d) => ()    {R1}         

Code. Der kategoriale Ansatz benötigt eine komplexere Kategoriesequenz für den Eintrag des Segments a.

 [sur:a, cat:(b c d)], [sur:b, cat:(b)], [sur:c, cat:(c)], [sur:d, cat:(d)]  

Darüber hinaus wird die Definition einer Variable (innerhalb einer spezifischen Variablendatei) benötigt, um die Regel R1 unabhängig vom nächsten Segment rekursiv anwenden zu können.

 string H <- {b c d}  

Die Regeldatei kann dafür sehr einfach gehalten werden. Durch die Verwendung der vordefinierten Variable “_” ist es möglich, Listen von beliebiger Länge abzugleichen, ohne auf weitere Kategoriewerte achten zu müssen.

 ST_S = {([cat: (b c d)], {R1})}
 
 R1 {R1}  [cat: (H _)] [cat: (H)]  concat(NW.sur SS.sur)
                                   cancel(H)
 
 ST_F = {([cat: ()] rp_R1)}  

Jede reguläre Sprache kann von einem endlichen Automaten geparst werden, welcher wiederum immer durch einen Kellerautomaten mit nur einem Zustand simuliert werden kann. Darüber hinaus kann ein einzelner Zustandsübergang eines Kellerautomaten von einer einzigen LAG-Regel simuliert werden. Dementsprechend ist es möglich, alle regulären Sprachen mit einer einzigen LAG-Regel zu parsen. Zustandsübergänge mit gleichem Input, aber verschiedenen Keller-Speichern, können mit Hilfe von Klauseln realisiert werden. Der Nachteil dieses Ansatzes liegt darin, dass die benötigten Kategorien sehr komplex werden können. Darüber hinaus ist dieser Ansatz nur realisierbar, wenn die zu parsende Sequenz einer vordefinierten Länge entspricht. Das bedeutet, dass Sprachen wie ab^kcd nicht auf diese Weise beschrieben werden können. Eine Lösung dieses Problems wird im Folgenden präsentiert.

Constraint-Ansatz, L = abcd

Mittels Constraints kann eine Beziehung zwischen Variablen spezifiziert werden. Durch die Verwendung eines Constraints zwischen zwei Variablen in einem Muster einer Klausel kann das Muster weiter verfeinert werden. Zudem ermöglichen Constraints die Vereinfachung der Kategoriewerte der Lexikoneinträge unter Beibehaltung eines einfachen Regelsystems.

Idee. Es wird ein constraint zwischen zwei Variablen definiert, der sicherstellt, dass die Kategorie des Satzanfangs mit der Kategorie des nächsten Segments übereinstimmt. Dies funktioniert folgendermaßen: Wenn das zuletzt eingelesene Segment ein a ist, so wird als nächstes nur ein b akzeptiert. Handelt es sich beim letzten Element um ein b, so wird nur ein c akzeptiert und so weiter. Um dies zu realisieren ist es nötig, dass die Kategorie des Satzanfangs nach jedem Kombinationsschritt angepasst wird.

Algorithmus. In diesem Fall ist es nicht mehr ausreichend, nur die Kategoriewerte des Satzanfangs und des nächsten Segments direkt aufeinander abzugleichen. Stattdessen muss beim Abgleich ein definierter constraint bearücksichtigt werden.

• [STS] Beginne mit Segment a und Regel R1.
• [R1 ] Sei x ∈ {a,b,c} die Kategorie des Satzanfangs und y ∈ {b,c,d} die Kategorie des nächsten Segments. Akzeptiere das nächste Segment nur, wenn x der Antezedent und y der Konsequent des entsprechenden constraints ist. Ersetze den Kategoriewert des Satzanfangs durch den des nächsten Segments und fahre mit Regel R1 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R1 beendet wurde und der Kategoriewert des Satzanfangs d ist.

Skizze. Die Ableitung entspricht einer Ableitung von L={a,b,c,d}⁺. Der Abgleich der constraints verläuft im Hintergrund.

 a.bcd  R1: (a)(b)     => (b)    {R1} 
 ab.cd  R1: (b)(c)     => (c)    {R1}
 abc.d  R1: (c)(d)     => (d)    {R1}

Code. Im Gegensatz zum kategorialen Ansatz bedient sich dieses Vorgehen eines sehr simplen Lexikons:

 [sur:a, cat:(a)], [sur:b, cat:(b)], [sur:c, cat:(c)], [sur:d, cat:(d)]  

Um constraints definieren zu können, werden zwei Variablen A und B benötigt. Erstere erfüllt die Rolle des Antezedenten, letztere die des Konsequenten. In der Variablendatei werden ihre grundsätzlichen Wertebereiche definiert und darüber hinaus wird spezifiziert, welche Werte sie in Abhängigkeit voneinander annehmen können.

 string A <- {a,b,c}
        B <- {b,c,d}
 
 constraint A  => B :
            a  => b .
            b  => c .
            c  => d . 

Ohne eine Verwendung des constraints würde die Grammatik die Sprache L=a{a,b,c,d}⁺d beschreiben. Um constraints zu verifizieren, genügt es, die Variablen des constraints in einem Regelmuster anzuwenden.

 
 ST_S = {([cat: (a)], {R1})}
 
 R1 {R1} [cat: (A)] [cat: (B)] set(B SS.cat.1)
                               concat(NW.sur SS.sur)
 
 ST_F = {([cat: (d)] rp_R1)} 
 

Das hier gezeigte Vorgehen ist dann nützlich, wenn die Sequenz in mehr als einer Regel vorkommt. In einem solchen Fall kann die Sequenz, anstatt als Teil der Regel selbst, als Metaregel angesehen werden. Hier wäre es dann angemessen, diese Sequenz gesondert von den Regeln zu definieren. Darüber hinaus erleichtern constraints die Modifizierung der Grammatik, so dass sie auch Sprachen akzeptiert, welche sich zu L = abcd ähnlich verhalten. Beispielsweise kann die Sprache L = (ab)+(cd)+ von einer Gramatik beschrieben werden, die exakt dieselbe Regel verwendet. Es müssen lediglich andere constraints verwendet werden. Der Unterschied dieses Ansatzes im Vergleich zum kategorialen liegt darin, dass die zu bearbeitende Sequenz nun nicht mehr einer vordefinierten Länge entsprechen muss (vgl. L = a^kb^lc^md^l). Von der exzessiven Verwendung von constraints sollte dennoch abgesehen werden, da sie dem Anwender das Lesen der Grammatik erschweren.

Kategorialer Ansatz, L = ab²c³d⁴

Die Sprache L umfasst nur ein einziges Wort, die Sequenz abbcccdddd. Wir verwenden erneut die Grammatik des kategorialen Ansatzes von abcd, ändern allerdings das Lexikon sowie die Definition des Startzustands.

Idee. Es wird eine festgelegte Reihenfolge von Segmenten bearbeitet. Dementsprechend kann diese starr definierte Sequenz im Lexikoneintrag des ersten Segments kodiert werden.

Algorithmus. Dieser Algorithmus ist identisch mit dem, der bereits für L = abcd benutzt wurde.

• [STS] Beginne mit dem Segment a und Regel R1.
• [R1] Stelle sicher, dass der Kategoriewert des nächsten Segments mit dem Wert identisch ist, der am linken Rand der Kategoriesequenz des Satzanfangs steht. Entferne diesen Wert und fahre mit Regel R1 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R1 beendet wurde und die Kategorie des Satzanfangs leer ist.

Skizze. Sei w=abbccdddd ∈ L.

 
 a.bbcccdddd R1: (b b c c c d d d d)(b) => (b c c c d d d d) {R1}     
 ab.bcccdddd R1:   (b c c c d d d d)(b) => (c c c d d d d )  {R1}     
 abb.cccdddd R1:     (c c c d d d d)(c) => (c c d d d d d)   {R1}     
 abbc.ccdddd R1:       (c c d d d d)(c) => (c d d d d d)     {R1}     
 abbcc.cdddd R1:         (c d d d d)(c) => (d d d d d)       {R1}     
 abbccc.dddd R1:           (d d d d)(d) => (d d d d)         {R1}     
 abbcccd.ddd R1:             (d d d)(d) => (d d d)           {R1}     
 abbcccdd.dd R1:               (d d)(d) => (d d)             {R1}     
 abbcccddd.d R1:                 (d)(d) => (d)               {R1}   

Code. Der einzige Unterschied zum Lexikon von L = abcd besteht darin, dass der Eintrag des Segments a, das in seiner Kategorie die gesamte Sequenz kodiert, angepasst werden muss.

 
 [sur:a,cat:(b b c c c d d d d)],[sur:b,cat:(b)],[sur:c,cat:(c)],[sur:d,cat:(d)] 
 

Die Variablendefinition kann beibehalten werden, da das einzige Wort der Sprache noch immer mit einem einzelnen a beginnt.

 string H <- {b,c,d} 
 

Das Muster des Satzanfangs muss angeglichen werden. Dies hätte durch die Verwendung einiger weiterer Variablen vermieden werden können.

 
 ST_S = {([cat: (b b c c c d d d d)], {R1})}
 
 R1 {R1} [cat: (H _)][cat: (H)] concat(NW.sur SS.sur)
                                cancel(SS.cat.1)
 
 ST_F = {([cat: ()] rp_R1)}

Komplexität. LAG: C1 (linear). Die Grammatik weist keine Ambiguitäten auf, da nur eine Regel existiert. PSG: regulär (linear). Die Sprache beschreibt nur ein Wort und ist somit problemlos mittels regulärer Ausdrücke beschreibbar. Dieses Beispiel zeigt, dass der kategoriale Ansatz wesentlich flexibler als sein primitives Äquivalent ist. Entsprechende Grammatiken können wesentlich einfacher erweitert werden. Der Nachteil liegt allerdings darin, dass die verwendeten Kategorien komplexer werden, was die Verarbeitung von aufwendigeren Sprachen erschwert.

Constraint Ansatz, L = a^kb^lc^mdⁿ

Die Sprache L beschreibt alle Wörter, die mit einer beliebigen Anzahl des Segments a beginnen, gefolgt von

• einer beliebigen Anzahl von Segmenten b, gefolgt von
• einer beliebigen Anzahl von Segmenten c, gefolgt von
• einer beliebigen Anzahl von Segmenten d.

Beispielwörter sind z.B. abcd, aabcd, aaabcd, aabccccccdddd etc. Um die korrekte Reihenfolge der Elemente sicher zu stellen, wird auf constraints zurückgegriffen. Die Grammatik bedient sich nur einer einzigen Regel und die Lexikoneinträge enthalten minimale Kategoriewerte.

Idee. Es wird ein constraint zwischen zwei Variablen definiert, der die Kategoriewerte des Satzanfangs und des jeweils nächsten Wortes aufeinander abgleicht. Dies funktioniert nach folgendem Schema: Falls zuletzt ein a eingelesen wurde, so kann dieses nur mit einem weiteren a oder einem b kombiniert werden. Auf die gleiche Weise wird dann mit b und c, bzw. darauf folgend mit c und d verfahren. Nachdem das zu lesende Element nur von dem gerade gelesenen Element abhängt, wird die Kategorie des Satzanfangs nach jedem Kombinationsschritt durch die des gelesenen Elements ersetzt.

Algorithmus. Der Algorithmus entspricht, erweitert um einen zusätzlichen constraint, dem des freien Monoids über {a,b,c,d}, der die richtige Reihenfolge der Segmente spezifiziert.

• [STS] Beginne mit einem Segment s ∈ {a,b,c,d} und der Regel R1.
• [R1 ] Sei x der Kategoriewert des Satzanfangs, y der des nächsten Segments und U und V zwei Variablen, die an diese Werte gebunden sind. Wende die Regel R1 dann und nur dann an, wenn x dem Antezedent und y dem Konsequent eines constraints zwischen den Variablen U und V entspricht.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R1 beendet wurde.

Skizze. Sei w=aabccddd ∈ L.

 
 a.abccddd  R1:  (a)(a) => (a) {R1}      
 aa.bccddd  R1:  (a)(b) => (b) {R1}      
 aab.ccddd  R1:  (b)(c) => (c) {R1}      
 aabc.cddd  R1:  (c)(c) => (c) {R1}      
 aabcc.ddd  R1:  (c)(d) => (d) {R1}      
 aabccd.dd  R1:  (d)(d) => (d) {R1}      
 aabccdd.d  R1:  (d)(d) => (d) {R1}      

Code. Erneut werden die Lexikoneinträge auf die einfachste Art und Weise definiert, indem jedem Element eine einzigartige, der Oberfläche entsprechende Kategorie zugeordnet wird.

 [sur:a, cat:(a)], [sur:b, cat:(b)], [sur:c, cat:(c)], [sur:d, cat:(d)] 

Die beiden Variablen U und V werden mitsamt eines constraints definiert, der der Einhaltung der korrekten Reihenfolge der Segmente innerhalb eines wohlgeformten Eingabewortes dient.

 string       U <- {a,b,c,d}
              V <- {a,b,c,d}
 
 constraint   U => V         :
              a => {a,b,c,d} .
              b => {b,c,d}   .
              c => {c,d}     .
              d => {d}       . 

Die beiden Variablen werden innerhalb des Regelmusters benutzt, um die Verwendung des constraints sicherzustellen.

 ST_S = {([cat: (U)] {R1})}
 
 R1 {R1} [cat: (U)][cat: (V)] concat(NW.sur SS.sur)
                              set(V SS.cat.1)
 
 ST_F = {([cat: (V)] rp_R1)} 

Dieses Beispiel verdeutlicht die Mächtigkeit von constraint-Variablen, da sie dazu benutzt werden können, Regeln zu vereinfachen und die Länge von Kategoriewerten zu reduzieren.

Elementare Rekursion, L = a^k

Die Sprache L enthält alle Sequenzen einer beliebigen Anzahl des Segments a, z.B. a, aa, aaa, aaaa, etc.

Idee. Rekursive Eingaben können von rekursiv arbeitenden Regeln geparst werden. Dementsprechend wird die Sprache von einer Regel beschrieben, die sich in ihrem Regelpaket selbst referenziert.

Algorithmus. Die verwendete Regel wird rekursiv angewandt.

• [STS] Beginne die Ableitung mit Segment a und Regel R1.
• [R1 ] Akzeptiere ausschließlich Segment a als nächstes Wort und fahre mit Regel R1 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R1 beendet wurde und der Kategoriewert des Satzanfangs a ist.

Skizze. Sei w=aaaa ∈ L.

 a.aaaa  R1:  (a)(a) => (a) {R1}      
 aa.aaa  R1:  (a)(a) => (a) {R1}      
 aaa.aa  R1:  (a)(a) => (a) {R1}      
 aaaa.a  R1:  (a)(a) => (a) {R1}      

Code. Es wird nur ein simpler Lexikoneintrag für das Segment a benötigt.

 [sur:a, cat:(a)] 

Die Regeldatei enthält folgende Einträge:

 
 ST_S = {([cat: (a)] {R1})}
 
 R1 {R1} [cat: (a)] [cat: (a)] concat(NW.sur SS.sur)
 
 ST_F = {([cat: (a)] rp_R1 rp_ST_S.1)}

Komplexität. LAG: C1 (linear). Die Grammatik weist keine Ambiguitäten auf, da nur eine Regel existiert. PSG: regulär (linear). Die Sprache ist problemlos mittels regulärer Ausdrücke beschreibbar (L=aa^*). Elementare Rekursion kann dadurch erzeugt werden, dass eine Regel in ihr eigenes Regelpaket aufgenommen wird. Die Kategorie des Satzanfangs muss erhalten bleiben. Elemantare Rekursion kann auch in natürlichen Sprachen auftreten. Ein Beispiel hierfür liefert der Satz “She is a beautiful nice little girl”.

Rekursion von Sequenzen, L = (abcd)^k

Die Sprache L enthält alle Wörter die eine beliebige Anzahl an Wiederholungen der Sequenz abcd darstellen, z.B. abcd, abcdabcd, abcdabcdabcd, etc.

Idee. An dieser Stelle wird auf die Grammatik von abcd zurückgegriffen, doch anstatt Elemente aus der Kategorie des Satzanfangs zu entfernen wird nur deren Reihenfolge verschoben (sprich: geshiftet). Es wird ein Kombinationsschritt mit dem nächsten Wort ausgeführt, wenn das erste Element seiner Kategorie dem zweiten Element der Kategorie des Satzanfangs entspricht.

Algorithmus. Hierbei handelt sich um einen einfachen shift-Algorithmus.

• [STS] Beginne die Ableitung mit dem Segment b und der Regel R1.
• [R1 ] Führe die Regel R1 dann und nur dann aus, wenn der Kategoriewert s ∈ {a,b,c,d} des nächsten Segments dem ersten Element des Kategoriewerts des Satzanfangs entspricht. Entferne das erste Element des Kategoriewerts des Satzanfangs und hänge es hinten wieder an. Fahre mit Regel R1 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R1 beendet wurde und das erste Element des Kategoriewerts des Satzanfangs a entspricht.

Skizze. Sei w=abcdabcd ∈ L

 
 a.bcdabcd  R1:(b c d a)(b)       => (c d a b)  {R1}      
 ab.cdabcd  R1:(c d a b)(c)       => (d a b c)  {R1}      
 abc.dabcd  R1:(d a b c)(d)       => (a b c d)  {R1}      
 abcd.abcd  R1:(a b c d)(b c d a) => (b c d a)  {R1}      
 abcda.bcd  R1:(b c d a)(b)       => (c d a b)  {R1}      
 abcdab.cd  R1:(c d a b)(c)       => (d a b c)  {R1}      
 abcdabc.d  R1:(d a b c)(d)       => (a b c d)  {R1}      

Code. Die Lexikoneinträge sind beinahe identisch mit denen der Sprache L = (abcd). Allerdings muss das Symbol a auf der rechten Seite der Kategoriesequenz des Segments a auftauchen, da die Elemente dieser Kategoriesequenz nicht gelöscht, sondern verschoben werden.

 [sur:a, cat:(b c d a)], [sur:b, cat:(b)], [sur:c, cat:(c)], [sur:d,cat:(d)] 

Regel R1 shiftet die Kategoriesequenz, indem das erste Element der Sequenz entfernt und am Ende wieder angefügt wird. Dabei wird im Muster für das nächste Segment lediglich der Wert am rechten Rand überprüft, da die Kategoriesequenz für den Eintrag des Segments a die gesamte verschobene Sequenz beinhaltet, aber immer noch den Kategoriewert a am Ende aufweist.

 ST_S = {([cat: (_)] {R1})}
 
 R1 {R1} [cat: (H _)] [cat: (_ H)] acopy(SS.cat.1 SS.cat)
                                   cancel(SS.cat.1)
                                   concat(NW.sur SS.sur)
 
 ST_F = {([cat: (a _)] rp_R1)}

Komplexität. LAG: C1 (linear). Die Grammatik weist keine Ambiguitäten auf, da nur eine Regel existiert. PSG: regulär (linear). Die Sprache ist problemlos mittels regulärer Ausdrücke beschreibbar (L=abcd(abcd)^*). Rekursive Sequenzen können durch das Verschieben von Elementen innerhalb einer Kategorie modelliert werden. Obwohl die meisten Sprachen mit sequenzieller Rekursion wesentlich anspruchsvoller sind, kann als grundsätzliche Regel gelten, dass kategoriale Informationen innerhalb eines Rekursionsschrittes erhalten bleiben sollten. Diese Regel kann auch auf natürliche Sprachen angewandt werden. Ein Beispiel für die Rekursion einer Sequenz von Wörtern in natürlicher Sprache liefert der folgende Satz: 'Der Mann gab dem Mädchen eine Blume, dem Jungen ein Spielzeug und der Katze eine Maus.'

Alternierende Rekursion, L = a^2k

Die Sprache L enthält alle Wörter, die aus einer geraden Anzahl des Segments a bestehen, z.B. aa, aaaa, aaaaaaaa, etc.

Idee. Hier wechseln sich die beiden Regeln R1 und R2 ab, wobei beide Regeln a einlesen. Wenn mit R2 begonnen wird, so garantiert der Abschluss mit R2, dass eine gerade Anzahl an a eingelesen wurde (wenn R2 das erste mal ausgeführt wird, kombiniert es zwei a -- das des im Startzustand definierten Satzanfangs und das des nächsten Wortes).

Algorithmus. Die beiden Regeln R1 und R2 müssen nur die Kategorie des nächsten Segments überprüfen und sich gegenseitig in ihren Regelpaketen referenzieren.

• [STS] Beginne die Ableitung mit dem Segment a und der Regel R2.
• [R1 ] Stelle sicher, dass es sich beim nächsten Segment um ein a handelt. Fahre mit Regel R2 fort.
• [R2 ] Stelle sicher, dass es sich beim nächsten Segment um ein a handelt. Fahre mit Regel R1 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R2 beendet wurde.

Skizze. Sei w = aaaaaa ∈ L

 a.aaaaa  R2:(a)(a)  => (a) {R1}      
 aa.aaaa  R1:(a)(a)  => (a) {R2}      
 aaa.aaa  R2:(a)(a)  => (a) {R1}      
 aaaa.aa  R1:(a)(a)  => (a) {R2}      
 aaaaa.a  R2:(a)(a)  => (a) {R1}      

Code. Es wird ein simpler Lexikoneintrag für das Segment a benötigt.

 [sur:a, cat:(a)] 

Die Regelpakete von R1 und R2 enthalten die jeweils andere Regel, wodurch die alternierende Rekursion ermöglicht wird. Es ist zu beachten, dass zuerst die Regel R2 ausgeführt wird, da im ersten Kombinationsschritt die ersten beiden Segmente miteinander verknüpft werden.

 ST_S = {([cat: (a)] {R2})}
 
 R1 {R2} [cat: (a)] [cat: (a)] concat(NW.sur SS.sur)
 R2 {R1} [cat: (a)] [cat: (a)] concat(NW.sur SS.sur)
 
 ST_F = {([cat: (a)] rp_R2)}

Komplexität. LAG: C1 (linear). Die Grammatik weist keine Ambiguitäten auf, da die Regelpakete maximal eine Regel referenzieren. PSG: regulär (linear). Die Sprache ist problemlos mittels regulärer Ausdrücke beschreibbar (L=aa(aa)^*). Diese Art der Rekursion kann manchmal nützlich sein, allerdings erschwert sie Erweiterungen. Vergleiche dazu den nächsten Abschnitt.

Alternierende Rekursion, L = a^3k

Die Sprache L enthält alle Wörter, deren Anzahl an Segmenten a ein Vielfaches von drei ist, z.B. aaa, aaaaaa, aaaaaaaaa, etc.

Idee. Hier wechseln sich die drei Regeln R1, R2 und R3 ab, wobei alle drei a einlesen. Wenn mit Regel R2 begonnen wird, so garantiert der Abschluss mit R3 die korrekte Anzahl an a.

Algorithmus. Diese Grammatik funktioniert auf die gleiche Weise wie die vorhergehende. Der Unterschied liegt darin, dass nun drei Regeln benötigt werden.

• [STS] Beginne die Ableitung mit dem Segment a und der Regel R2.
• [R1 ] Stelle sicher, dass es sich beim nächsten Segment um ein a handelt. Fahre mit Regel R2 fort.
• [R2 ] Stelle sicher, dass es sich beim nächsten Segment um ein a handelt. Fahre mit Regel R3 fort.
• [R3 ] Stelle sicher, dass es sich beim nächsten Segment um ein a handelt. Fahre mit Regel R1 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R3 beendet wurde.

Skizze. Sei w = aaaaaa ∈ L.

 a.aaaaa  R2:(a)(a) => (a)  {R3}      
 aa.aaaa  R3:(a)(a) => (a)  {R1}      
 aaa.aaa  R1:(a)(a) => (a)  {R2}      
 aaaa.aa  R2:(a)(a) => (a)  {R3}      
 aaaaa.a  R3:(a)(a) => (a)  {R1}      

Code. Es wird ein simpler Lexikoneintrag für das Segment a benötigt.

 [sur:a, cat:(a)] 

Die Regelpakete von R1, R2 und R3 enthalten die jeweils nachfolgende Regel (im Sinne der Namensgebung), wodurch die alternierende Rekursion ermöglicht wird. Zu beachten ist, dass zuerst die Regel R2 ausgeführt wird, da im ersten Kombinationsschritt die ersten beiden Segmente miteinander verknüpft werden.

 ST_S = {([cat: (a)] {R2})}
 
 R1 {R2} [cat: (a)] [cat: (a)] concat(NW.sur SS.sur)
 R2 {R3} [cat: (a)] [cat: (a)] concat(NW.sur SS.sur)
 R3 {R1} [cat: (a)] [cat: (a)] concat(NW.sur SS.sur)
 
 ST_F = {([cat: (a)] rp_R3)}

Komplexität. LAG: C1 (linear). Die Grammatik weist keine Ambiguitäten auf, da die Regelpakete maximal eine Regel referenzieren. PSG: regulär (linear). Die Sprache ist problemlos mittels regulärer Ausdrücke beschreibbar (L=aaa(aaa)^*). Dieses “copy and paste”-Vorgehen deutet darauf hin, dass es eine elegantere Methode zum Schreiben einer solchen Grammatik gibt. Jede Sprache L ∈ {L | L =a^ik, i =2,3,..,n} benötigt i Regeln. Dementsprechend wird dieser Ansatz umso schwieriger umzusetzen, desto größer i wird. Abgesehen davon sind die hier benötigten Regeln so speziell, dass sie kaum erweiterbar sind.

Kategorialer Ansatz, L = a^2k

Die Sprache L enthält alle Wörter, deren Anzahl an Segmenten a ein Vielfaches von zwei ist, z.B. aa, aaaa, aaaaaa, aaaaaaaa, etc.

Idee. Der Wechsel zweier Regeln wird bei diesem Ansatz durch das Vertauschen der Kategorie des Satzanfangs simuliert. Dieses Vorgehen kann immer dann angewandt werden, wenn sich die Regeln ausschließlich durch ihr Regelpaket unterscheiden.

Algorithmus. Es wird nur eine einzige Regel benötigt.

• [STS] Beginne die Ableitung mit dem Segment a und der Regel R1.
• [R1 ] Stelle sicher, dass es sich beim nächsten Segment um ein a handelt. Entferne den ersten Wert in der Kategoriesequenz des Satzanfangs und hänge ihn hinten wieder an. Fahre mit Regel R1 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R1 beendet wurde und der erste Wert in der Kategoriesequenz des Satzanfangs den Wert b hat.

Skizze. Sei w=aaaaaa ∈ L.

 a.aaaaa  R1: (a b)(a) => (b a)  {R1}      
 aa.aaaa  R1: (b a)(a) => (a b)  {R1}      
 aaa.aaa  R1: (a b)(a) => (b a)  {R1}      
 aaaa.aa  R1: (b a)(a) => (a b)  {R1}      
 aaaaa.a  R1: (a b)(a) => (b a)  {R1}      

Code. Die Kategorie für den Lexikoneintrag a besteht aus einer Liste zweier verschiedener Werte, um modulo zwei ausführen zu können, indem die beiden Elemente miteinander getauscht werden.

 [sur:a, cat:(a b)] 

Die Variable H dient dazu, nicht zwischen den zwei Zuständen unterscheiden zu müssen, bei denen entweder a oder b das erste Kategoriesegment des Satzanfangs bilden.

 string H <- {a,b} 

Die Regel R1 gibt an, dass das nächste Segment ein a ist. Die Elemente der Kategoriesequenz werden vertauscht, indem das Element am Anfang entfernt und am Ende angehängt wird.

 ST_S = {([cat: (a _)] {R1})}
 
 R1 {R1} [cat: (H _)] [cat: (a _)] concat(NW.sur SS.sur)
                                   acopy(H SS.cat)
                                   cancel(H)
 
 ST_F = {([cat: (b _)] rp_R1)}  

Dieser Ansatz ist nicht nur kompakter, sondern darüber hinaus ist die verwendete Regel sehr viel genereller formuliert. Dies ermöglicht einfachere Erweiterung und Verbesserung, wie der nächste Abschnitt zeigen wird.

Kategorialer Ansatz, L = a^3k

Die Sprache L enthält alle Wörter, die aus einer Sequenz a bestehen, wobei die Anzahl der a einem Vielfachen von drei entspricht, z.B. aaa, aaaaaa, aaaaaaaaa, etc.

Idee. Es wird eine Liste der Länge drei verwendet, in der die Elemente rotieren, um modulo drei zu zählen. Dabei muss ein Element der Liste unterschiedlich zu den anderen sein, um feststellen zu können, wann der Originalzustand der Liste wieder erreicht ist. Der Algorithmus arbeitet nach demselben Vorgehen wie bei der Grammatik für die Sprache L=a^2k}, es wird lediglich das Lexikon verändert.

Skizze. Sei w=aaaaaa ∈ L

 a.aaaaa  R1:(a b a)(a b a) => (a a b)  {R1}      
 aa.aaaa  R1:(a a b)(a b a) => (b a a)  {R1}      
 aaa.aaa  R1:(b a a)(a b a) => (a b a)  {R1}      
 aaaa.aa  R1:(a b a)(a b a) => (a a b)  {R1}      
 aaaaa.a  R1:(a a b)(a b a) => (b a a)  {R1}      

Code. Das zweite Listenelement ist verschieden zu den anderen, da die Kategoriesequenz des Lexikoneintrags der Anfangskategorie des Satzanfangs entspricht.

 [sur:a, cat:(a b a)] 

Zu beachten ist, dass das Regelsystem allgemein genug ist, um jeder Sprache L ∈ {L | L =a^{ik}, i =2,3,..n} zu parsen. Die nötigen Veränderungen beziehen sich nur auf das Lexikon.

Vereinigung, primitiver Ansatz: L = a^2k ∪ a^3k

Die Sprache L enthält alle Wörter, die aus einer Sequenz von a bestehen, wobei die Anzahl der Segmente entweder dem Vielfachen von zwei, dem Vielfachen von drei oder beidem entspricht. Beispielwörter sind aa, aaa, aaaa, aaaaaa, aaaaaaaa, aaaaaaaaa, etc.

Idee. Die Vereinigung der (primitiven) Grammatiken durch das bloße Zusammenfügen der Regeln und des Lexikons ist nicht möglich, da dieses Vorgehen zu einer ambigen Grammatik führen würde, die für all jene Eingaben, die von beiden Sprachen akzeptiert werden (wie bspw. a^6}) zwei Resultate liefern würde. Folglich ist die automatische Wiederverwendung der Komponenten kaum mehr möglich. Das kleinste gemeinsame Vielfache von zwei und drei ist sechs. Für jedes x=1...6 bestimmt man, ob a^x zur Sprache gehört.

• a¹=a not ∈ L
• a²=aa ∈ L (2 = 0 mod 2)
• a³=aaa ∈ L (3 = 0 mod 3)
• a⁴=aaaa ∈ L (4 = 0 mod 2)
• a⁵=aaaaa not ∈ L
• a⁶=aaaaaa ∈ L (6 = 0 mod 2)

Algorithmus.

• [STS] Beginne mit Segment a und Regel R2.
• [R1 ] Stelle sicher, dass es sich beim nächsten Segment um ein a handelt. Fahre mit Regel R2 fort.
• [R2 ] Stelle sicher, dass es sich beim nächsten Segment um ein a handelt. Fahre mit Regel R3 fort.
• [R3 ] Stelle sicher, dass es sich beim nächsten Segment um ein a handelt. Fahre mit Regel R4 fort.
• [R4 ] Stelle sicher, dass es sich beim nächsten Segment um ein a handelt. Fahre mit Regel R5 fort.
• [R5 ] Stelle sicher, dass es sich beim nächsten Segment um ein a handelt. Fahre mit Regel R6 fort.
• [R6 ] Stelle sicher, dass es sich beim nächsten Segment um ein a handelt. Fahre mit Regel R1 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R2, R3, R4 oder R6 beendet wurde.

Skizze. Sei w=aaaaaaaa ∈ L

 a.aaaaaaa  R2:(a)(a)  => (a)  {R3}      
 aa.aaaaaa  R3:(a)(a)  => (a)  {R4}      
 aaa.aaaaa  R4:(a)(a)  => (a)  {R5}      
 aaaa.aaaa  R5:(a)(a)  => (a)  {R6}      
 aaaaa.aaa  R6:(a)(a)  => (a)  {R1}      
 aaaaaa.aa  R1:(a)(a)  => (a)  {R2}      
 aaaaaaa.a  R2:(a)(a)  => (a)  {R3}      

Code. Benötigt wird ein einfacher Lexikoneintrag für a.

 [sur:a, cat:(a)] 

Die Wohlgeformtheit einer Eingabe wird allein dadurch bestimmt, indem die jeweilige vorhergehende Regel der Endzustandsdefinition hinzugefügt wird.

 ST_S = {([cat: (a)] {R2})}
 
 R1 {R2} [cat: (a)][cat: (a)] concat(NW.sur SS.sur)
 R2 {R3} [cat: (a)][cat: (a)] concat(NW.sur SS.sur)
 R3 {R4} [cat: (a)][cat: (a)] concat(NW.sur SS.sur)
 R4 {R5} [cat: (a)][cat: (a)] concat(NW.sur SS.sur)
 R5 {R6} [cat: (a)][cat: (a)] concat(NW.sur SS.sur)
 R6 {R1} [cat: (a)][cat: (a)] concat(NW.sur SS.sur)
 
 ST_F = {([cat: (a)] rp_R2 rp_R3 rp_R4 rp_R6)}

Komplexität. LAG: C1 (linear). Die Grammatik weist keine Ambiguitäten auf, da die Regelpakete maximal eine Regel referenzieren. PSG: regulär (linear). Die Sprache ist problemlos mittels regulärer Ausdrücke beschreibbar (L=aa(aa)^*|aaa(aaa)^*). Der Nachteil dieses Ansatzes sollte offensichtlich sein: Die Anzahl an Regeln ist gestiegen. Selbst wenn dieses Vorgehen auf den ersten Blick den Eindruck vermittelt, äußerst effektiv zu sein, ist es kaum möglich, eine solche Grammatik zu erweitern.

Vereinigung, kategorialer Ansatz: L = a^2k ∪ a^3k

Idee. Das kleinste gemeinsame Vielfache von zwei und drei ist sechs. Zudem ist a¹ not ∈ L, a² ∈ L, a³ ∈ L, a⁴ ∈ L, a⁵ not ∈ L, a⁶ ∈ L. Sei nun n ∈ N und r = n mod 6. aⁿ ∈ L dann und nur dann, wenn x not ∈ {1,5}. Diese Information kann mit der Kategoriesequenz “(a b b b a b)” realisiert werden. Ein Kategoriewert b an der Position p gibt an, dass das Wort w=aⁿ ∈ L wenn n = p mod 6. Schiebt man nun die Liste bei jedem Ableitungsschritt weiter, kann durch das Überprüfen des Kategoriewerts am linken Rand überprüft werden, ob das Wort zu der Sprache gehört. Da jedes Anfangssegment ein a ist, verwendet man die Kategoriesequenz “(a b b b a b)” für den Lexikoneintrag des Segments a, die somit als Kategoriesequenz des Satzanfangs gesetzt wird.

Skizze. Sei w=aaaaaaaa ∈ L

 a.aaaaaaa  R1:  (a b b b a b)(a b b b a b) => (b b b a b a)  {R1}
 aa.aaaaaa  R1:  (b b b a b a)(a b b b a b) => (b b a b a b)  {R1}
 aaa.aaaaa  R1:  (b b a b a b)(a b b b a b) => (b a b a b b)  {R1}
 aaaa.aaaa  R1:  (b a b a b b)(a b b b a b) => (a b a b b b)  {R1}
 aaaaa.aaa  R1:  (a b a b b b)(a b b b a b) => (b a b b b a)  {R1}
 aaaaaa.aa  R1:  (b a b b b a)(a b b b a b) => (a b b b a b)  {R1}
 aaaaaaa.a  R1:  (a b b b a b)(a b b b a b) => (b b b a b a)  {R1}

Code. Das Lexikon beinhaltet einen Lexikoneintrag für das Segment a mit der Kategoriesequenz “(a b b b a b)”. Die Grammatik akzeptiert kein einzelnes Segment a als wohlgeformt, da der Kategoriewert am linken Rand ein a ist.

 [sur:a, cat:(a b b b a b)] 

Man benötigt eine Variable H, die a oder b als möglichen ersten Wert der Satzanfangskategoriesequenz akzeptiert.

 string H <- {a, b} 

Die Grammatik besteht aus einer einzigen Regel, welche den ersten Wert der Kategoriesequenz des Satzanfangs löscht und am Ende anhängt. Ein Ausdruck ist wohlgeformt, wenn nach dem letzten Schritt der erste Wert der Kategoriesequenz b ist. Das Regelsystem ist identisch mit demjenigen für die Sprachen L=a^2k und L=a^3k.

 ST_S = {([cat: (a b b b a b)], {R1})}
 
 R1 {R1} [cat: (H _)] [cat: (a _)]   concat(NW.sur SS.sur)
                                     acopy(H SS.cat)
                                     cancel(H)
 
 ST_F = {([cat: (b _)] rp_R1)} 

Die Anzahl an Regeln kann durch geschickten Entwurf der Kategorien reduziert werden.

Kontextfreie Sprachen

L = a^kb^k

Die Sprache L enthält alle Wörter, die mit einer beliebigen Anzahl an a beginnen, gefolgt von genau derselben Anzahl an b, z.B. ab, aabb, aaabbb, aaaabbbb, etc. Diese einfache Struktur kann beispielsweise dazu verwendet werden, um verschachtelte Relativsätze in den natürlichen Sprachen zu modellieren.

Idee. Für jedes eingelesene Wort a wird ein a in der Kategorie des Satzanfangs gespeichert. Falls das Wort b eingelesen wird, wird ein a aus der Kategorie des Satzanfangs gelöscht. Das Ergebnis wird akzeptiert, wenn die Kategoriesequenz nach der Ableitung leer ist.

Algorithmus. Die Grammatik besteht aus zwei Regeln: eine, um die Segmente a zu verarbeiten (R1) und eine, um die Segmente b zu verarbeiten (R2). R1 kann nicht nach R2 ausgeführt werden. Auf diese Weise wird nicht nur garantiert, dass die Anzahl der Segmente a mit der Anzahl der Segmente b übereinstimmt, sondern dass auch die Segmente a und b in der korrekten Reihenfolge erscheinen.

• [STS] Stelle sicher, dass es sich beim ersten Segment um ein a handelt. Beginne mit Regel R1 und R2.
• [R1 ] Stelle sicher, dass es sich beim nächsten Segment um ein a handelt. Speichere den Kategoriewert a am linken/rechten Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R1 und R2 fort.
• [R2 ] Stelle sicher, dass es sich beim nächsten Segment um ein b handelt. Entferne den Kategoriewert a aus der Kategoriesequenz des Satzanfangs. Fahre mit Regel R2 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R2 beendet wurde und die Kategoriesequenz des Satzanfangs leer ist.

Skizze. Sei w=aaabbb ∈ L

 a.aabbb  R1   (a)(a) => (aa)  {R1,R2}
 aa.abbb  R1  (aa)(a) => (aaa) {R1,R2}
 aaa.bbb  R2 (aaa)(b) => (aa)  {R1,R2}
 aaab.bb  R2  (aa)(b) => (a)   {R1,R2}
 aaabb.b  R2   (a)(b) => ()    {R1,R2}

Code. Hinsichtlich der Kategorien der Einträge sind keine Besonderheiten zu berücksichtigen. Die Werte a und b müssen allerdings unterscheidbar sein.

 [sur:a, cat:(a)], [sur:b, cat:(b)] 

Bei der Regel R1 ist es nicht nötig, die Kategoriesequenz des Satzanfangs zu überprüfen, da die Startzustandsdefinition und die prozedurale Semantik des Regelschemas annimmt, dass es nur aus dem Wert a besteht. Regel R2 stellt hingegen sicher, dass die Kategoriesequenz nicht leer ist.

 ST_S = {([cat: (a)], {R1 R2})}
 
 R1 {R1 R2} [cat: (_)]   [cat: (a)] concat(NW.sur SS.sur)
                                    acopy(a SS.cat)
 R2 {R2}    [cat: (a _)] [cat: (b)] concat(NW.sur SS.sur)
                                    cancel(SS.cat.1)
 ST_F = {([cat: ()] rp_R2)}

Komplexität. LAG: C1 (linear). Die Grammatik weist keine Ambiguitäten auf, da die Eingabebedingungen der Regeln R1 und R2 hinsichtlich des nächsten Segments inkompatibel sind. PSG: kontextfrei (polynomial). Es besteht eine binär inverse Korrespondenz (k in a^kb^k).

L = a^kb^kc^md^m

Die Sprache L enthält alle Wörter, die

• mit einer beliebigen Anzahl an Segmenten a beginnen, gefolgt von
• genau derselben Anzahl an Segmenten b, gefolgt von
• einer beliebigen Anzahl an Segmenten c, gefolgt von
• genau derselben Anzahl an Segmenten d.

Beispielwörter sind abcd, aabbcd, aaabbbcd, abccdd, etc.

Idee. Sei L_1 = a^kb^k und L_2 = c^md^m, L = L_1,L_2. Somit kann die Grammatik für L=a^k b^k wiederverwendet und erweitert werden, indem man die Regeln dupliziert. R1 und R2 sind die ursprünglichen Regeln und R3 und R4 ihre entsprechenden Kopien. Da R2 von der Endzustandsdefinition der ursprünglichen Grammatik referenziert wird, wird R3 zusätzlich in deren Regelpaket hinzugefügt. Dabei ist zu beachten, dass nicht alle Kopien angefügt werden können, die den referenzierten Regeln aus der Startzustandsdefinition entsprechen. Schließlich werden die Kopien der ursprünglich von der Grammatik referenzierten Regeln mit der Endzustandsdefinition der neuen Grammatik verknüpft.

Algorithmus.

• [STS] Stelle sicher, dass es sich beim ersten Segment um ein a handelt. Beginne mit Regel R1 und R2.
• [R1 ] Stelle sicher, dass es sich beim nächsten Segment um ein a handelt. Speichere den Kategoriewert a am linken/rechten Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R1 und R2 fort.
• [R2 ] Stelle sicher, dass es sich beim nächsten Segment um ein b handelt. Entferne den Kategoriewert b aus der Kategoriesequenz des Satzanfangs. Fahre mit Regel R2 und R3 fort.
• [R3 ] Stelle sicher, dass es sich beim nächsten Segment um ein c handelt. Speichere den Kategoriewert c am linken/rechten Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R3 und R4 fort.
• [R4 ] Stelle sicher, dass es sich beim nächsten Segment um ein d handelt. Entferne den Kategoriewert c aus der Kategoriesequenz des Satzanfangs. Fahre mit Regel R4 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R4 beendet wurde und die Kategoriesequenz des Satzanfangs leer ist.

Code. Es werden Lexikoneinträge für die Segmente a, b, c und d benötigt, die in ihrem Kategoriewert unterscheidbar sein müssen.

 [sur:a, cat:(a)][sur:b, cat:(b)][sur:c, cat:(c)][sur:d, cat:(d)] 

Zu beachten ist, dass lediglich R3 in das Regelpaket von R2 eingefügt wurde, da mindestens ein Segment c erwartet wird.

 ST_S = {([cat: (a)], {R1, R2})}
 
 R1 {R1 R2}  [cat: (_)  ] [cat: (a)] concat(NW.sur SS.sur)
                                     acopy(a SS.cat)
 
 R2 {R2 R3}  [cat: (a _)] [cat: (b)] concat(NW.sur SS.sur)
                                     cancel(SS.cat.1)
 
 R3 {R3 R4}  [cat: (_)  ] [cat: (c)] concat(NW.sur SS.sur)
                                     acopy(c SS.cat)
 
 R4 {R4}     [cat: (c _)] [cat: (d)] concat(NW.sur SS.sur)
                                     cancel(SS.cat.1)
 
 ST_F = {([cat: ()] rp_R4)}

Komplexität. LAG: C1 (linear). Die Grammatik weist keine Ambiguitäten auf, da die Eingabebedingungen der Regeln R1, R2, R3 und R4 hinsichtlich des folgenden Segments inkompatibel sind. PSG: kontextfrei (polynomial). Es bestehen zwei binär inverse Korrespondenzen (k in a^kb^k und m in c^md^m).

L = a^kb^mc^md^k

Die Sprache L enthält alle Wörter, die mit einer beliebigen Anzahl an Segmenten a beginnen, gefolgt von einer beliebigen Anzahl an Segmenten b, gefolgt von einer zu b identischen Anzahl an Segmenten c, gefolgt von einer zu a identischen Anzahl an Segmenten d. Beispielwörter sind abcd, aabcdd, abbccd, aaabcddd, etc.

Idee. Speichere für jedes Segment a den Kategoriewert a in der Kategorie des Satzanfangs am linken/rechten Rand. Speichere für jedes Segment b den Kategoriewert a in der Kategorie des Satzanfangs am linken/rechten Rand. Lösche für jedes Segment c ein a aus der Kategoriesequenz des Satzanfangs. Lösche für jedes Segment d ein a aus der Kategoriesequenz des Satzanfangs. Akzeptiere, wenn die Satzanfangs-Kategorie am Ende der Ableitung leer ist.

Algorithmus. Der Algorithmus ähnelt dem für a^kb^kc^md^m. Allerdings müssen im Gegensatz dazu alle Segmente a und b gespeichert werden, um diese anschließend mit der Anzahl der Segmente c und d abgleichen zu können.

• [STS] Stelle sicher, dass es sich beim ersten Segment um ein a handelt. Beginne mit Regel R1 und R2.
• [R1 ] Stelle sicher, dass es sich beim nächsten Segment um ein a handelt. Speichere den Kategoriewert a am linken/rechten Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R1 und R2 fort.
• [R2 ] Stelle sicher, dass es sich beim nächsten Segment um ein b handelt. Speichere den Kategoriewert b am linken/rechten Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R2 und R3 fort.
• [R3 ] Stelle sicher, dass es sich beim nächsten Segment um ein c handelt. Entferne den Kategoriewert b aus der Kategoriesequenz des Satzanfangs. Fahre mit Regel R3 und R4 fort.
• [R4 ] Stelle sicher, dass es sich beim nächsten Segment um ein d handelt. Entferne den Kategoriewert a aus der Kategoriesequenz des Satzanfangs. Fahre mit Regel R4 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R4 beendet wurde und die Kategoriesequenz des Satzanfangs leer ist.

Skizze. Sei w=aabbbcccdd ∈ L

 a.abbbcccdd  R1:     (a)(a) => (aa)    {R1,R2}
 aa.bbbcccdd  R2:    (aa)(b) => (aab)   {R2,R3}
 aab.bbcccdd  R2:   (aab)(b) => (aabb)  {R2,R3}
 aabb.bcccdd  R2:  (aabb)(b) => (aabbb) {R2,R3}
 aabbb.cccdd  R3: (aabbb)(c) => (aabb)  {R3,R4}
 aabbbc.ccdd  R3:  (aabb)(c) => (aab)   {R3,R4}
 aabbbcc.cdd  R3:   (aab)(c) => (aa)    {R3,R4}
 aabbbccc.dd  R4:    (aa)(d) => (a)     {R4}
 aabbbcccd.d  R4:     (a)(d) => ()      {R4}

Code. Es werden Lexikoneinträge für die Segmente a, b, c und d benötigt, die in ihrem Kategoriewert unterscheidbar sein müssen.

 [sur:a, cat:(a)][sur:b, cat:(b)][sur:c, cat:(c)][sur:d, cat:(d)] 

Zu beachten ist, dass die Regeln R1, R2, R3 und R4 inkompatible Eingabebedingungen haben, da sich die jeweiligen Kategoriewerte des nächsten Wortes unterscheiden. 

 ST_S = {([cat: (a)], {R1, R2})}
 
 R1 {R1 R2} [cat: (_)  ] [cat: (a)] concat(NW.sur SS.sur)
                                    acopy(a SS.cat)
 R2 {R2 R3} [cat: (_)  ] [cat: (b)] concat(NW.sur SS.sur)
                                    acopy(b SS.cat)
 R3 {R3 R4} [cat: (_ B)] [cat: (c)] concat(NW.sur SS.sur)
                                    cancel(B)
 R4 {R4}    [cat: (_ A)] [cat: (d)] concat(NW.sur SS.sur)
                                    cancel(A)
 
 ST_F = {([cat: ()] rp_R4)}

Komplexität. LAG: C1 (linear). Die Grammatik weist keine Ambiguitäten auf, da die Eingabebedingungen der Regeln R1, R2, R3 und R4 hinsichtlich des nächsten Segments inkompatibel sind. PSG: kontextfrei (polynomial). Es bestehen zwei binär inverse Korrespondenzen (k in a^k ... d^k and m in b^mc^m).

Vereinigung, prim. Ansatz: L = a^kb^kc^md^m ∪ a^kb^mc^md^k

Die Sprache L enthält alle Wörter, die entweder der Sprache L_1 = a^kb^kc^md^m oder der Sprache L_2=a^kb^mc^md^k angehören. Das bedeutet, dass die Sprache alle Wörter beinhaltet, die lediglich die Segmente a, b, c und d enthalten. Dabei kommt kein Segment b vor einem Segment a, kein Segment c vor einem Segment b und kein Segment d vor einem Segment c vor. Zusätzlich entspricht entweder die Anzahl der Segmente a der Anzahl der Segmente b und die Anzahl der Segmente c der Anzahl der Segmente d oder die Anzahl der Segmente a der Anzahl der Segmente d und die Anzahl der Segmente b der Anzahl der Segmente c.

Idee. Erstelle Regeln für a^kb^kc^md^m und füge die Regeln für a^kb^mc^md^k hinzu. Die daraus resultierende Grammatik wird allerdings doppelte Ergebnisse liefern für jedes w ∈ a^kb^kc^md^m ∪ a^kb^mc^md^k.

Algorithmus. Die Regeln R1, R2, R3 und R4 entsprechen den Regeln für die Sprache L = a^kb^kc^md^m und sind identisch mit R1, R2, R3 und R4. Die Regeln R1, R5, R6 und R7 entsprechen den Regeln für die Sprache L = a^kb^mc^md^k und sind identisch mit den Regeln R1, R2, R3 und R4.

• [STS] Stelle sicher, dass es sich beim ersten Segment um ein a handelt. Beginne mit Regel R1 und R2.
• [R1 ] Stelle sicher, dass es sich beim nächsten Segment um ein a handelt. Speichere den Kategoriewert a am linken/rechten Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R1, R2 und R5 fort.
• [R2 ] Stelle sicher, dass es sich beim nächsten Segment um ein b handelt. Entferne den Kategoriewert a aus der Kategoriesequenz des Satzanfangs. Fahre mit Regel R2 und R3 fort.
• [R3 ] Stelle sicher, dass es sich beim nächsten Segment um ein c handelt. Speichere den Kategoriewert c am linken/rechten Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R3 und R4 fort.
• [R4 ] Stelle sicher, dass es sich beim nächsten Segment um ein d handelt. Entferne den Kategoriewert c aus der Kategoriesequenz des Satzanfangs. Fahre mit Regel R4 fort.
• [R5 ] Stelle sicher, dass es sich beim nächsten Segment um ein b handelt. Speichere den Kategoriewert b am linken/rechten Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R5 und R6 fort.
• [R6 ] Stelle sicher, dass es sich beim nächsten Segment um ein c handelt. Entferne den Kategoriewert b aus der Kategoriesequenz des Satzanfangs. Fahre mit Regel R6 und R7 fort.
• [R7 ] Stelle sicher, dass es sich beim nächsten Segment um ein d handelt. Entferne den Kategoriewert c aus der Kategoriesequenz des Satzanfangs. Fahre mit Regel R7 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R4 oder R7 beendet wurde und die Kategoriesequenz des Satzanfangs leer ist.

Code. Es werden Lexikoneinträge für die Segmente a, b, c und d benötigt, die in ihrem Kategoriewert unterscheidbar sein müssen.

 [sur:a, cat:(a)], [sur:b, cat:(b)], [sur:c, cat:(c)], [sur:d, cat:(d)] 

 

 ST_S = {([cat: (a)], {R1, R2, R5})}
 
 R1 {R1 R2 R5} [cat: (_)][cat: (A)] concat(NW.sur SS.sur)
                                    acopy(A _ 1)
 R2 {R2 R3} [cat: (A _)][cat: (b)]  concat(NW.sur SS.sur)
                                    cancel(A)
 R3 {R3 R4} [cat: (_)  ][cat: (c)]  concat(NW.sur SS.sur)
                                    acopy(c _ 1)
 R4 {R4}    [cat: (C _)][cat: (d)]  concat(NW.sur SS.sur)
                                    cancel(C)
 R5 {R5 R6} [cat: (_)][cat: (B)]    concat(NW.sur SS.sur)
                                    acopy(B _ 1)
 R6 {R6 R7} [cat: (B _)][cat: (c)]  concat(NW.sur SS.sur)
                                    cancel(B)
 R7 {R7} [cat: (A _)][cat: (d)]     concat(NW.sur SS.sur)
                                    cancel(A)
 ST_F = {([cat: ()] rp_R4 rp_R7)}

Komplexität. LAG: C1 (linear). Die Grammatik weist Ambiguitäten auf, da die Eingabebedingungen der Regeln R2 und R5 kompatibel sind. Die Ambiguität ist allerdings nicht rekursiv. PSG: kontextfrei (polynomial). Die kontextfreien Sprachen sind in der Vereinigung enthalten.

L = ww^R

Die Sprache L enthält alle Wörter, die Wörter gerader Länge spiegeln, d.h. alle Wörter mit einer bestimmten Sequenz am Anfang und der umgedrehten Sequenz im Anschluss, z.B. aa, bb, abba, aaaa, aabbbbaa, etc.

Idee. Bei jedem Kombinationsschritt wird entweder w oder w^R bearbeitet. R1 geht davon aus, dass der Parser noch dabei ist, einen Teil von w einzulesen und speichert dementsprechend ein Kategoriesymbol in umgedrehter Reihenfolge. R2 geht hingegen davon aus, dass w^R verarbeitet wird und stellt deshalb sicher, dass das einzulesende Wort dem geforderten entspricht.

Algorithmus. Es werden zwei Regeln benötigt: R1 speichert die Segmente des ersten w, R2 stellt sicher, dass die Segmente von w^R mit den bereits gespeicherten übereinstimmen.

• [STS] Stelle sicher, dass es sich beim ersten Segment um das erste Segment aus w handelt und behalte den zugehörigen Kategoriewert. Beginne mit Regel R1 und R2.
• [R1 ] Stelle sicher, dass es sich beim nächsten Segment um ein Segment aus w handelt. Speichere dessen Kategoriewert am linken Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R1 und R2 fort.
• [R2 ] Stelle sicher, dass das nächste Segment mit dem entsprechenden Segment aus w übereinstimmt, indem dessen Kategoriewert mit dem am linken Rand gespeicherten Wert der Kategoriesequenz des Satzanfangs übereinstimmt. Entferne den Kategoriewert am linken Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R2 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R2 beendet wurde und die Kategoriesequenz des Satzanfangs leer ist.

Skizze. Sei w=abcdaadcba ∈ L.

 a.bcdaadcba  R1: (a)(b)     => (ba)           {R1, R2}
 ab.cdaadcba  R1: (ba)(c)    => (cba)          {R1, R2}
 abc.daadcba  R1: (cba)(d)   => (dcba)         {R1, R2}
 abcd.aadcba  R1: (dcba)(a)  => (adcba)        {R1, R2}
 abcda.adcba  R2: (adcba)(a) => (dcba)         {R2}
 abcdaa.dcba  R2: (dcba)(d)  => (cba)          {R2}
 abcdaad.cba  R2: (cba)(c)   => (ba)           {R2}
 abcdaadc.ba  R2: (ba)(b)    => (a)            {R2}
 abcdaadcb.a  R2: (a)(a)     => ()             {R2}

Code. Für den vorliegenden Algorithmus ist es lediglich notwendig, dass sich die Lexikoneinträge hinsichtlich des Kategoriewerts unterscheiden.

 [sur:a, cat:(a)], [sur:b, cat:(b)], [sur:c, cat:(c)], [sur:d, cat:(d)] 

Man benötigt eine Variable, um den Kategoriewert jedes beliebigen Segments aus w abzugleichen.

 string L <- {a,b,c,d} 

Die Grammatik besteht aus den Regeln R1 und R2, die w bzw. w^R verarbeiten.

 ST_S = {([cat: (_)], {R1 R2})}
 
 R1 {R1 R2}   [cat: (_)]     [cat: (L)]  concat(NW.sur SS.sur)
                                         acopy(L SS.cat 1)
 R2 {R2}      [cat: (L _)] [cat: (L)]    concat(NW.sur SS.sur)
                                         cancel(SS.cat.1)
 
 ST_F = {([cat: ()] rp_R2)}

Komplexität. LAG: C2 (linear). Die Grammatik weist Ambiguitäten auf, da die Eingabebedingungen der Regeln R1 und R2 kompatibel sind. Die Ambiguität ist -SRP rekursiv, da das Regelpaket der Regel R1 die Regeln R1 und R2 referenziert, wohingegen das Regelpaket der Regel R2 lediglich sich selbst referenziert. PSG: kontextfrei (polynomial). Es besteht eine binär inverse Korrespondenz (w w^R).

Kontextsensitive Sprachen

L = ww

Die Sprache L enthält alle Wörter, deren erste Hälfte der Sequenz mit denen der zweiten Hälfte identisch ist, z.B. aa, abab, abcabc, aaaaaa, etc. Die triviale Konsequenz ist, dass alle Wörter aus einer geraden Anzahl an Sequenzen bestehen.

Idee. Das Vorgehen ähnelt dem bei der Grammatik für L = ww^R. Zunächst speichert man für jedes Segment des ersten w einen repräsentativen Kategoriewert und entfernt diesen Wert wieder für jeden korrespondierenden Kategoriewert des zweiten w. Für das Löschen der Kategoriewerte wird dabei auf die gegenüberliegende Seite zugegriffen.

Skizze. Sei w=abcaabca ∈ L

 a.bcaabca  R1:    (a)(b) => (ab)   {R1,R2}
 ab.caabca  R1:   (ab)(c) => (abc)  {R1,R2}
 abc.aabca  R1:  (abc)(a) => (abca) {R1,R2}
 abca.abca  R2: (abca)(a) => (bca)  {R2}
 abcaa.bca  R2:  (bca)(b) => (ca)   {R2}
 abcaab.ca  R2:   (ca)(c) => (a)    {R2}
 abcaabc.a  R2:    (a)(a) => ()     {R2}

Algorithmus. Es werden zwei Regeln benötigt: eine speichert die Segmente des ersten w (R1), eine weitere stellt sicher, dass die Segmente des zweiten w mit den gespeicherten Segmenten übereinstimmen (R2).

• [STS] Stelle sicher, dass es sich beim ersten Segment um ein mögliches Segment aus w handelt. Beginne mit Regel R1 und R2.
• [R1 ] Stelle sicher, dass es sich beim nächsten Segment um ein mögliches Segment aus w handelt. Speichere dessen Kategoriewert am rechten Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R1 und R2 fort.
• [R2 ] Stelle sicher, dass das nächste Segment mit dem entsprechenden Segment aus w übereinstimmt, indem dessen Kategoriewert mit dem am linken Rand gespeicherten Wert der Kategoriesequenz des Satzanfangs verglichen wird. Entferne den Kategoriewert am linken Rand der Kategoriesequenz. Fahre mit Regel R2 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R2 beendet wurde und die Kategoriesequenz des Satzanfangs leer ist.

Code. Für den vorliegenden Algorithmus ist es lediglich notwendig, dass sich die Lexikoneinträge hinsichtlich des Kategoriewerts unterscheiden.

 [sur:a, cat:(a)], [sur:b, cat:(b)], [sur:c, cat:(c)], [sur:d, cat:(d)] 

Man benötigt eine Variable, um den Kategoriewert jedes beliebigen Segments aus w abzugleichen.

 string L <- {a,b,c,d} 

Die Regel R1 unterscheidet sich insofern von R1 für die Sprache L=ww^R, als dass die Kategoriewerte an den rechten und nicht an den linken Rand angehängt werden.

 ST_S = {([cat: (_)], {R1 R2})}      
 
 R1 {R1 R2} [cat: (_)  ] [cat: (L)]  concat(NW.sur SS.sur)
                                     acopy(L SS.cat)                                    
 R2 {R2}    [cat: (L _)] [cat: (L)]  concat(NW.sur SS.sur)
                                     cancel(SS.cat.1)
 
 ST_F = {([cat: ()] rp_R2)}

Komplexität. LAG: C2 (polynomial). Die Grammatik weist Ambiguitäten auf, da die Eingabebedingungen der Regeln R1 und R2 kompatibel sind. Die Ambiguität ist -SRP rekursiv, da das Regelpaket der Regel R1 die Regeln R1 und R2 referenziert, wohingegen das Regelpaket der Regel R2 lediglich sich selbst referenziert. PSG: kontextsensitiv (exponentiell). Es besteht eine binäre, aber nicht inverse Korrespondenz (w w).

Einfacher Trenner, L = www

Die Sprache L beinhaltet alle Sequenzen, die aus einer dreifachen Wiederholung einer Subsequenz bestehen, z.B. aaa, ababab, abcabcabc, aaaaaaaaa, etc. Die triviale Konsequenz ist, dass die Wortlänge ein Vielfaches von drei beträgt.

Idee. Speichere einen aussagekräftigen Kategoriewert für jedes Segment des ersten w und shifte durch die Kategoriesequenz für jedes Segment des zweiten w. Dabei wird angenommen, dass beide w miteinander korrespondieren. Das letzte zu shiftende Segment wird mittels eines einfachen Trenners markiert. Lösche für jedes Segment des dritten w den korrespondierenden Kategoriewert aus der Kategoriesequenz und akzeptiere das Ergebnis als gültig, wenn nur noch das Trennsymbol übrig ist.

Algorithmus. Benötigt werden vier Regeln, jeweils eine für jedes w und eine, um das Trennsymbol einzufügen.

• [STS] Beginne mit einem beliebigen Segment aus w und den Regeln R1 und R2.
• [R1] Speichere für jedes Segment des ersten w einen entsprechenden Kategoriewert am rechten Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R1 und R2 fort.
• [R2] Füge am rechten Rand der Kategoriesequenz des Satzanfangs ein Trennsymbol an. Stelle sicher, dass der Kategoriewert des nächsten Segments dem Wert auf der linken Seite der Kategoriesequenz des Satzanfangs entspricht. Entferne den Wert am linken Rand der Kategoriesequenz und speichere den Wert am rechten Rand. Fahre mit Regel R3 und R4 fort.
• [R3] Vergleiche für jedes zusätzliche Segment des zweiten w den Kategoriewert mit dem Wert am linken Rand der Kategoriesequenz des Satzanfangs. Speichere diesen Wert am rechten Rand und entferne ihn vom linken. Fahre mit Regel R3 und R4 fort.
• [R4] Entferne für jedes Segment des dritten w den entsprechenden Kategoriewert vom linken Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R3 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R3 beendet wurde und die Kategoriesequenz des Satzanfangs leer ist.

Skizze. Sei w=abab ∧ www ∈ L

 
 a.bababababab  R1:      (a)(b) => (ab)     {R1,R2}
 ab.ababababab  R1:     (ab)(a) => (aba)    {R1,R2}
 aba.babababab  R1:    (aba)(b) => (abab)   {R1,R2}
 abab.abababab  R2:   (abab)(a) => (babta)  {R3,R4}
 ababa.bababab  R3:  (babta)(b) => (abtab)  {R3,R4}
 ababab.ababab  R3:  (abtab)(a) => (btaba)  {R3,R4}
 abababa.babab  R3:  (btaba)(b) => (tabab)  {R3,R4}
 abababab.abab  R4:  (tabab)(a) => (tbab)   {R4}
 ababababa.bab  R4:   (tbab)(b) => (tab)    {R4}
 ababababab.ab  R4:    (tab)(a) => (tb)     {R4}
 abababababa.b  R4:     (tb)(b) => (t)      {R4}

Code. Für den vorliegenden Algorithmus ist es lediglich notwendig, dass sich die Lexikoneinträge hinsichtlich des Kategoriewerts unterscheiden. Für das Trennsymbol ist kein Lexikoneintrag notwendig.

 [sur:a, cat:(a)], [sur:b, cat:(b)], [sur:c, cat:(c)], [sur:d, cat:(d)] 

Man benötigt eine Variable, um den Kategoriewert jedes beliebigen Segments aus w abzugleichen.

 string L <- {a,b,c,d} 

Zu beachten ist, dass die Regeln R1 und R2 kompatible Eingabebedingungen, die Regeln R3 und R4 aber inkompatible Eingabebedingungen besitzen.

 ST_S = {([cat: (_)], {R1 R2})}
 
 R1 {R1,R2} [cat: (_)  ] [cat: (L)]   concat(NW.sur SS.sur)
                                      acopy(L SS.cat)  
 R2 {R3,R4} [cat: (L _)] [cat: (L)]   concat(NW.sur SS.sur)
                                      acopy(t L SS.cat)
                                      cancel(SS.cat.1)                                     
 R3 {R3,R4} [cat: (L _)] [cat: (L)]   concat(NW.sur SS.sur)
                                      acopy(L SS.cat)
                                      cancel(SS.cat.1)                                     
 R4 {R4}    [cat: (t L _)] [cat: (L)] concat(NW.sur SS.sur)
                                      cancel(SS.cat.2)
 
 ST_F = {([cat: (t)] rp_R4)}

Komplexität. LAG: C2 (polynomial). Die Grammatik weist Ambiguitäten auf, da die Eingabebedingungen der Regeln R1 und R2 kompatibel sind. Die Ambiguität ist -SRP rekursiv, da das Regelpaket der Regel R1 die Regeln R1 und R2 referenziert, wohingegen das Regelpaket der Regel R2 nicht zu der Ambiguität zurückführt. PSG: kontextsensitiv (exponentiell). Es besteht weder eine binäre noch eine inverse Korrespondenz.

Marker, L = www

Idee. Speichere einen entsprechenden Kategoriewert für jedes Segment des ersten w, shifte die Kategoriesequenz für jedes Segment des zweiten w durch und füge dabei vor jedes Symbol einen Marker ein. Dabei wird sichergestellt, dass beide w korrespondieren. Lösche für jedes Segment des dritten w den entsprechenden Kategoriewert und den vorangestellten Marker aus der Kategoriesequenz und akzeptiere das Ergebnis als gültig, wenn die Kategoriesequenz leer ist.

Algorithmus. Es sind drei Regeln notwendig, eine für jedes w.

• [STS] Beginne mit mit einem beliebigen Segment aus w und der Regel R1 und R2.
• [R1] Speichere für jedes Segment des ersten w einen entsprechenden Kategoriewert am rechten Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R1 und R2 fort.
• [R2] Vergleiche den Kategoriewert jedes Segments des zweiten w mit dem Kategoriewert am linken Rand der Kategoriesequenz des Satzanfangs. Entferne den Wert am linken Rand und speichere diesen mit vorangestelltem Marker, welcher sich von den möglichen Werten für w unterscheiden muss, am rechten Rand. Fahre mit Regel R2 und R3 fort.
• [R3] Entferne für jedes Segment des dritten w den entsprechenden Kategoriewert und den vorangestellten Marker vom linken Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R3 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R3 beendet wurde und die Kategoriesequenz des Satzanfangs leer ist.

Skizze. Sei w=abav ∧ www ∈ L

 a.bababababab  R1:       (a)(b) => (ab)      {R1,R2}
 ab.ababababab  R1:      (ab)(a) => (aba)     {R1,R2}
 aba.babababab  R1:     (aba)(b) => (abab)    {R1,R2}
 abab.abababab  R2:    (abab)(a) => (babta)   {R2,R3}
 ababa.bababab  R2:   (babta)(b) => (abtatb)  {R2,R3}
 ababab.ababab  R2:  (abtatb)(a) => (btatbta) {R2,R3}
 abababa.babab  R2: (btatbta)(b) => (tatbtatb){R2,R3}
 abababab.abab  R3:(tatbtatb)(a) => (tbtatb)  {R3}
 ababababa.bab  R3:  (tbtatb)(b) => (tatb)    {R3}
 ababababab.ab  R3:    (tatb)(a) => (tb)      {R3}
 abababababa.b  R3:      (tb)(b) => ()        {R3}

Code. Sei w ∈ {a,b,c,d}. Für die Lexikoneinträge bietet es sich an, jede Oberfläche mit einem der Oberfläche entsprechenden Kategoriewert zu versehen.

 [sur:a, cat:(a)], [sur:b, cat:(b)], [sur:c, cat:(c)], [sur:d, cat:(d)] 

Abgesehen von der Nummerierung sind die Regeln R1 und R3 identisch mit den Regeln R1 und R4 der Grammatik L=www.

 ST_S = {([cat: (_)], {R1 R2})}
 
 R1 {R1 R2} [cat: (_)  ] [cat: (L)]   concat(NW.sur SS.sur)
                                      acopy(L SS.cat)                                     
 R2 {R2 R3} [cat: (L _)] [cat: (L)]   concat(NW.sur SS.sur)
                                      acopy(t L SS.cat)
                                      cancel(SS.cat.1)                                     
 R3 {R3}    [cat: (t L _)] [cat: (L)] concat(NW.sur SS.sur)
                                      cancel(SS.cat.1)
                                      cancel(SS.cat.1)
 
 ST_F = {([cat: ()] rp_R3)} 

Durch die Verwendung von Markern entstehen zwar längere Kategoriesequenzen, allerdings wird das Verständnis der Grammatik vereinfacht. Zudem ist es nicht nötig, den ersten Schritt des Durchshiftens mit einer eigenen Regel zu behandeln.

L = w₁w₂w₁^Rw₂^R, |w₁| ≥ 2 ∧ |w₂| ≥ 1

Die Sprache L enthält alle Wörter, die

• mit einer aus mindestens zwei Segmenten bestehenden Sequenz w₁ beginnen, gefolgt von
• einer nichtleeren Sequenz w₂, gefolgt von
• der gespiegelten Sequenz von w₁, gefolgt von
• der gespiegelten Sequenz von w₂.

Idee. Die Segmente werden eingelesen und für jedes wird ein Wert am Ende der Kategorieliste gespeichert (R1). Nach jedem Kombinationsschritt kann das Ende von w₁ erreicht sein oder nicht. Deshalb müssen beide Möglichkeiten in Betracht gezogen und dementsprechend zwei alternative Pfade gleichzeitig verfolgt werden. Wenn man annimmt, dass das Ende von w₁ noch nicht erreicht ist, wird auf die gleiche Weise fortgefahren wie vor der Ausführung von R1. Im anderen Fall fügt man ein Trennsymbol am Anfang der Kategorie ein und speichert die Kategoriewerte von nun an am Anfang der Liste (R2). Am Ende jedes Kombinationsschritts muss überprüft werden, ob w₂ vollständig eingelesen wurde oder nicht. Dazu führt man entweder das Speichern der Kategorie am Listenanfang fort (R3), oder beginnt damit, das letzte Element der Liste zu löschen, falls dieses mit dem Kategoriewert des nächsten Wortes übereinstimmt (R4). Falls das letzte Symbol der Kategorieliste das Trennzeichen ist, wird immer das erste Element der Kategorieliste gelöscht. Eine Eingabe wird dann als korrekt akzeptiert, wenn das Trennzeichen als einziges Symbol in der Kategorie des Satzanfangs erhalten bleibt.

Algorithmus.

• [STS] Stelle sicher, dass es sich beim ersten Segment um ein mögliches Segment aus w₁ handelt. Beginne mit Regel R1.
• [R1 ] Stelle sicher, dass es sich beim nächsten Segment um ein mögliches Segment aus w₁ handelt. Speichere den entsprechenden Kategoriewert am rechten Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R1 und R2 fort.
• [R2 ] Stelle sicher, dass es sich beim nächsten Segment um ein mögliches Segment aus w₂ handelt. Speichere ein Trennsymbol und den korrespondierenden Wert zu dem Segment aus w₂ am linken Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R3 und R4 fort.
• [R3 ] Stelle sicher, dass es sich beim nächsten Segment um ein mögliches Segment aus w₂ handelt. Speichere den korrespondierenden Wert am linken Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R3 und R4 fort.
• [R4 ] Stelle sicher, dass es sich beim nächsten Segment um ein mögliches Segment aus w₁^R handelt, indem dessen Kategoriewert mit dem Wert am rechten Rand der Kategoriesequenz des Satzanfangs verglichen wird. Fahre mit Regel R4 und R5 fort.
• [R5 ] Stelle sicher, dass es sich beim nächsten Segment um ein mögliches Segment aus w₂^R handelt, indem dessen Kategoriewert mit dem Wert am linken Rand der Kategoriesequenz des Satzanfangs verglichen wird. Fahre mit Regel R5 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R5 beendet wurde und die Kategoriesequenz des Satzanfangs lediglich das Trennsymbol enthält.

Skizze. Sei w₁ = aab, w₂ = cd und w₁ w₂ ∈ L

 a.abcdbaadc  R1:            (a)(a) => (a a)         {R1,R2}   
 aa.bcdbaadc  R1:          (a a)(b) => (a a b)       {R1,R2}   
 aab.cdbaadc  R2:        (a a b)(c) => (c t a a b)   {R3,R4}   
 aabc.dbaadc  R3:    (c t a a b)(d) => (d c t a a b) {R3,R4}   
 aabcd.baadc  R4:  (d c t a a b)(b) => (d c t a)     {R4,R5}   
 aabcdb.aadc  R4:    (d c t a a)(a) => (d c t a)     {R4,R5}   
 aabcdba.adc  R4:      (d c t a)(a) => (d c t)       {R4,R5}   
 aabcdbaa.dc  R5:        (d c t)(d) => (c t)         {R5}      
 aabcdbaad.c  R5:          (c t)(c) => (t)           {R5}      

Code. Für den vorliegenden Algorithmus ist es lediglich notwendig, dass sich die Lexikoneinträge hinsichtlich der Kategoriewerte unterscheiden.

 [sur:a, cat:(a)], [sur:b, cat:(b)], [sur:c, cat:(c)], [sur:d, cat:(d)] 

Für die Kategoriewerte jedes potentiellen Segments aus w_i muss eine Variable definiert werden.

 string L <- {a,b,c,d} 

Da nun ein Marker verwendet wird, können die Regeln R2 und R3 aus der Grammatik für zusammengeführt werden.

 ST_S = {([cat: (L)] {R1})}
 
 R1 {R1 R2}  [cat: (_)    ] [cat: (L)]  concat(NW.sur SS.sur)
                                        acopy(L SS.cat)
 R2 {R3 R4}  [cat: (_)    ] [cat: (L)]  concat(NW.sur SS.sur)
                                        acopy(L t SS.cat 1)
 R3 {R4 R5}  [cat: (_)    ] [cat: (L)]  concat(NW.sur SS.sur)
                                        acopy(L SS.cat 1)
 R4 {R4 R5}  [cat: (_ L)  ] [cat: (L)]  concat(NW.sur SS.sur)
                                        cancel(SS.cat.1R)
 R5 {R5}     [cat: (L _ t)] [cat: (L)]  concat(NW.sur SS.sur)
                                        cancel(SS.cat.1)
 
 ST_F = {([cat: (t)] rp_R5)}  

Marker, L = w₁w₂w₁^Rw₂^R, |w₁| ≥ 2 ∧ |w₂| ≥ 1

Idee. In der vorliegenden Grammatik wird jedem gespeicherten Kategoriewert aus w₂ ein Trennsymbol vorangestellt.

Algorithmus.

• [STS] Stelle sicher, dass es sich beim ersten Segment um ein mögliches Segment aus w₁ handelt. Beginne mit Regel R1.
• [R1 ] Stelle sicher, dass es sich beim nächsten Segment um ein mögliches Segment aus w₁ handelt. Speichere den entsprechenden Kategoriewert am rechten Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R1 und R2 fort.
• [R2 ] Stelle sicher, dass es sich beim nächsten Segment um ein mögliches Segment aus w₂ handelt. Speichere ein Trennsymbol und den korrespondierenden Wert zu dem Segment aus w₂ am linken Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R2 und R3 fort.
• [R3 ] Stelle sicher, dass es sich beim nächsten Segment um ein mögliches Segment aus w₁^R handelt, indem dessen Kategoriewert mit dem Wert am rechten Rand der Kategoriesequenz des Satzanfangs verglichen wird. Fahre mit Regel R3 und R4 fort.
• [R4 ] Stelle sicher, dass es sich beim nächsten Segment um ein mögliches Segment aus w₂^R handelt, indem dessen Kategoriewert mit dem zweiten Wert am linken Rand der Kategoriesequenz des Satzanfangs verglichen wird; am linken Rand muss das Trennsymbol stehen. Entferne die ersten beiden Werte am linken Rand und fahre mit Regel R4 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R4 beendet wurde und die Kategoriesequenz des Satzanfanges leer ist.

Skizze. Sei w₁ = aab, w₂ = cd und w₁ w₂ ∈ L

 
 a.abcdbaadc  R1:            (a)(a) => (a a)           {R1,R2}   
 aa.bcdbaadc  R1:          (a a)(b) => (a a b)         {R1,R2}   
 aab.cdbaadc  R2:        (a a b)(c) => (c t a a b)     {R2,R3}   
 aabc.dbaadc  R2:    (c t a a b)(d) => (d t c t a a b) {R2,R3}   
 aabcd.baadc  R3:(d t c t a a b)(b) => (d t c t a a)   {R3,R4}   
 aabcdb.aadc  R3:  (d t c t a a)(a) => (d t c t a)     {R3,R4}   
 aabcdba.adc  R3:    (d t c t a)(a) => (d t c t)       {R3,R4}   
 aabcdbaa.dc  R4:      (d t c t)(d) => (c t)           {R4}      
 aabcdbaad.c  R4:          (c t)(c) => ()              {R4}     

Code. Für den vorliegenden Algorithmus ist es lediglich notwendig, dass sich die Lexikoneinträge hinsichtlich der Kategoriewerte unterscheiden. Für das Trennsymbol ist kein Lexikoneintrag notwendig.

 [sur:a, cat:(a)], [sur:b, cat:(b)], [sur:c, cat:(c)], [sur:d, cat:(d)] 

Zu beachten ist, dass die Eingabebedingungen der Regeln R3 und R4 inkompatibel sind. Der Marker wird nicht bei Regel R4 als Element an zweiter Stelle spezifiziert, da möglicherweise nur zwei Elemente in der Kategoriesequenz vorhanden sein können.

 ST_S = {([cat: (L)] {R1})}
 
 R1 {R1 R2}  [cat: (_)    ] [cat: (L)]  concat(NW.sur SS.sur)
                                        acopy(L SS.cat)
 R2 {R3 R4}  [cat: (_)    ] [cat: (L)]  concat(NW.sur SS.sur)
                                        acopy(L t SS.cat 1)
 R3 {R3 R4}  [cat: (_ L)  ] [cat: (L)]  concat(NW.sur SS.sur)
                                        cancel(SS.cat.1R)
 R4 {R4}     [cat: (L _ t)] [cat: (L)]  concat(NW.sur SS.sur)
                                        cancel(SS.cat.1)
                                        cancel(SS.cat.1)
 
 ST_F = {([cat: ()] rp_R4)}  

L = w₁ a w₂ a w₃ a w₂^R w₁^R w₃^R , w_i ∈ {b,c,d}⁺

Die Sprache L enthält alle Wörter x, wobei x mit einer nichtleeren Sequenz w₁ ∈ {b, c, d}⁺ beginnt, gefolgt von

• einem einzelnen Segment a,
• einer nichtleeren Sequenz w₂ ∈ {b,c,d}⁺,
• einem einzelnen Segment a,
• einer nichtleeren Sequenz w₃ ∈ {b, c, d}⁺,
• der gespiegelten Sequenz w₂,
• der gespiegelten Sequenz w₁ und
• der gespiegelten Sequenz w₃.

Der interessante Aspekt dieser Sprache ist dabei, dass drei Sequenzen derart gespeichert werden müssen, dass auf deren Segmente sequenziell zugegriffen werden kann. Das ist nicht immer mit einer Liste möglich, bei der nur auf deren Enden zugegriffen werden kann.

Idee. Die Sequenz aus w₁, w₂ und w₃ muss in der Kategorie des Satzanfangs gespeichert werden, um die Übereinstimmung mit der korrespondierenden Sequenz w₂^R w₁^R w₃^R zu garantieren. Dafür werden zwischen den gespeicherten Sequenzen Trenner benötigt, um deren Grenzen zu markieren. Da als erstes auf das letzte Segment aus w₂ zugegriffen werden muss, speichert man sämtliche Sequenzen in der Reihenfolge des Auftretens am rechten Rand der Kategoriesequenz des Satzanfangs. Das letzte Segment aus w₂ ist somit auch das letzte Segment des Satzanfangs. Als nächstes muss auf das letzte Segment aus w₁ zugegriffen werden. Dafür wird w₁ ebenfalls in der Reihenfolge des Auftretens gespeichert, also noch vor w₂. Um sicherzustellen, dass das letzte Segment aus w₂ das letzte Segment der Satzanfangskategorie bleibt, wird w₃ in umgedrehter Reihenfolge am linken Rand der Satzanfangskategorie gespeichert. Die Sequenzen w₁, w₂ und w₃ werden somit in der Reihenfolge w₃^R w₁ w₂ gespeichert. Das Zeichen a fungiert dabei als Trenner, da es nicht Bestandteil von w_i ist.

Algorithmus. Eine LA-Grammatik für L könnte folgendermaßen implementiert werden:

• [STS] Beginne mit einem Segment s ∈ {b,c,d} und Regel R1.
• [R1 ] Speichere für jedes Segment s aus w₁ s am rechten Rand der Kategoriesequenz des Satzanfangs.
• [R2 ] Speichere für das Segment a den Trenner a am rechten Rand der Kategoriesequenz des Satzanfangs.
• [R3 ] Speichere für jedes Segment s aus w₂ s am Ende der Kategoriesequenz des Satzanfangs.
• [R4 ] Speichere für das Segment a den Trenner a am linken Rand der Kategoriesequenz des Satzanfangs.
• [R5 ] Speichere für jedes Segment s aus w₃ s am linken Rand der Kategoriesequenz des Satzanfangs.
• [R6 ] Mache nichts für das Segment a.
• [R7 ] Lösche für jedes Segment s aus w₂^R das entsprechende Segment am rechten Rand der Kategoriesequenz des Satzanfangs.
• [R8 ] Lösche für jedes Segment s aus w₁^R das vorletzte Segment am rechten Rand der Kategoriesequenz des Satzanfangs. Das letzte Segment muss das Trennsegment a sein.
• [R9 ] Lösche für jedes Segment s aus w₃^R das entsprechende erste Segment am linken Rand der Kategoriesequenz des Satzanfangs.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R9 beendet wurde und die Kategoriesequenz lediglich aus zwei Trennsymbolen besteht.

Skizze. Sei w₁=bc,w₂=bd und w₃=cd

 
 b.cabdacdadbcbdc  R1:        (b)(c) => (bc)       {R1,R2}
 bc.abdacdadbcbdc  R2:       (bc)(a) => (bca)      {R3}
 bca.bdacdadbcbdc  R3:      (bca)(b) => (bcab)     {R3,R4}
 bcab.dacdadbcbdc  R3:     (bcab)(d) => (bcabd)    {R3,R4}
 bcabd.acdadbcbdc  R4:    (bcabd)(a) => (abcabd)   {R5}
 bcabda.cdadbcbdc  R5:   (abcabd)(c) => (cabcabd)  {R5,R6}
 bcabdac.dadbcbdc  R5:  (cabcabd)(d) => (dcabcabd) {R5,R6}
 bcabdacd.adbcbdc  R6: (dcabcabd)(a) => (dcabcabd) {R7}
 bcabdacda.dbcbdc  R7: (dcabcabd)(d) => (dcabcab)  {R7,R8}
 bcabdacdda.bcbdc  R7:  (dcabcab)(b) => (dcabca)   {R7,R8}
 bcabdacddab.cbdc  R8:   (dcabca)(c) => (dcaba)    {R8,R9}
 bcabdacddabc.bdc  R8:    (dcaba)(b) => (dcaa)     {R8,R9}
 bcabdacddabcb.dc  R9:     (dcaa)(d) => (caa)      {R9}
 bcabdacddabcbd.c  R9:      (caa)(d) => (aa)       {R9}

Code. Für den vorliegenden Algorithmus ist es lediglich notwendig, dass sich die Lexikoneinträge hinsichtlich der Kategoriewerte unterscheiden.

 [sur:a, cat:(a)], [sur:b, cat:(b)], [sur:c, cat:(c)], [sur:d, cat:(d)] 

Das Regelschema gibt den Algorithmus und die deklarative Spezifikation direkt wieder. Die Variable L ∈ {b,c,d} dient dazu, die Segmente aus w₁, w₂ und w₃ zusammenzufassen.

 ST_S={([cat: (L)] {R1,R2})}       
   
 R1 {R1,R2} [cat: (X)][cat: (L)]       concat(NW.sur SS.sur)
                                       acopy(L SS.cat)
 R2 {R3}    [cat: (X)][cat: (a)]       concat(NW.sur SS.sur)
                                       acopy(a SS.cat)
 R3 {R3,R4} [cat: (X)][cat: (L)]       concat(NW.sur SS.sur)
                                       acopy(L SS.cat)
 R4 {R5}    [cat: (X)][cat: (a)]       concat(NW.sur SS.sur)
                                       acopy(a SS.cat 1)
 R5 {R5,R6} [cat: (X)][cat: (L)]       concat(NW.sur SS.sur)
                                       acopy(L SS.cat 1)
 R6 {R7}    [cat: (X)][cat: (a)]       concat(NW.sur SS.sur)
 R7 {R7,R8} [cat: (X L)][cat: (L)]     concat(NW.sur SS.sur)
                                       cancel(SS.cat.1R)
 R8 {R8,R9} [cat: (X L a)][cat: (L)]   concat(NW.sur SS.sur)
                                       cancel(SS.cat.2R)
 R9 {R9}    [cat: (L X)][cat: (L)]     concat(NW.sur SS.sur)
                                       cancel(SS.cat.1)
 
 ST_F = {([cat: (a a)] rp_R9)}

Komplexität. LAG: C1 (linear). Es gibt keine Ambiguitäten, weil a als Trenner fungiert. Allerdings wäre L eine C2-LAG, wenn
w_i ∈ {a,b,c,d}⁺. PSG: kontextsensitiv (exponentiell): Die Korrespondenzen sind weder binär (ww...w^R) noch invers (ww).

L = w^Rw^Ra^|w|w , |w| = 2k, k > 0,w ∈ {a,b,c}⁺

Die Definition der Sprache L kann vereinfacht werden: L = wwa^|w|w^R. Die Sprache enthält alle Wörter, die mit einem Präfix w von gerader Länge n beginnen, gefolgt von

• dem identischen Präfix,
• n a, d.h. genauso viele a wie w Segmente hat und
• der gespiegelten Sequenz des Präfixes.

Algorithmus. Eine Grammatik für L könnte folgendermaßen implementiert werden:

• [STS] Beginne mit einem Segment s ∈ {a, b, c} und Regel R1.
• [R1 ] Speichere für jedes Segment s an gerader Position innerhalb des ersten Auftretens des Präfixes w an gerader Position eine entsprechende Kategorie am rechten Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R1u und R2 fort.
• [R1u] Speichere für jedes Segment s an ungerader Position innerhalb des ersten Auftretens des Präfixes w eine entsprechende Kategorie am rechten Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R1 fort.
• [R2 ] Speichere für jedes Segment s innerhalb des zweiten Auftretens des Präfixes w eine entsprechende Kategorie, gefolgt von einem Trenner, am rechten Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R3 fort.
• [R3 ] Stelle für jedes Segment s innerhalb des dritten Auftretens des Präfixes w sicher, dass der Wert am linken Rand der Kategoriesequenz des Satzanfangs mit dem Wert des nächsten Segments übereinstimmt. Shifte die Kategoriesequenz des Satzanfangs nach links und fahre mit Regel R3 und R4 fort.
• [R4 ] Stelle für jedes Segment a sicher, dass der erste Wert der Kategoriesequenz des Satzanfangs nicht der Kategoriewert des Trenners ist. Shifte die Kategoriesequenz des Satzanfangs nach links und fahre mit Regel R4 und R5 fort.
• [R5 ] Stelle für jedes Segment s sicher, dass der vorletzte Wert der Kategoriesequenz des Satzanfangs mit dem nächsten Segment übereinstimmt. Fahre mit Regel R5 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R5 beendet wurde und die Kategoriesequenz lediglich den Trenner beinhaltet.

Skizze. Sei w=abcabcaaacba ∈ L

 a.bcabcaaacba  R1: (a)(b)       => (a b)     {R1u,R2} 
 ab.cabcaaacba  R2: (a b)(c)     => (a b c t) {R3} 
 abc.abcaaacba  R3: (a b c t)(a) => (b c t a) {R3, R4} 
 abca.bcaaacba  R3: (b c t a)(b) => (c t a b) {R3, R4} 
 abcab.caaacba  R3: (c t a b)(c) => (t a b c) {R3, R4} 
 abcabc.aaacba  R4: (t a b c)(a) => (c t a b) {R4, R5} 
 abcabca.aacba  R4: (c t a b)(a) => (b c t a) {R4, R5} 
 abcabcaa.acba  R4: (b c t a)(a) => (a b c t) {R4, R5} 
 abcabcaaa.cba  R5: (a b c t)(c) => (a b t)   {R5} 
 abcabcaaac.ba  R5: (a b t)(b)   => (a t)     {R5} 
 abcabcaaacb.a  R5: (a t)(a)     => (t)       {R5} 

Code. Zu beachten ist, dass die Regel R1u, welche das Trennsymbol t einfügt, während der kompletten Ableitung nur ein einziges Mal ausgeführt wird.

 ST_S={([cat: (a)] {R1, R2})}
 
 R1  {R1u,R2}[cat:(X)    ][cat:(L)] acopy(L SS.cat)
 R1u {R1}    [cat:(X)    ][cat:(L)] acopy(L SS.cat)
 R2  {R3}    [cat:(X)    ][cat:(L)] acopy(L t SS.cat)
 R3  {R3,R4} [cat:(L X)  ][cat:(L)] acopy(L SS.cat)
                                    cancel(SS.cat.1)
 R4  {R4,R5} [cat:(X L)  ][cat:(a)] acopy(L SS.cat.1)
                                    cancel(SS.cat.1R)
 R5  {R5}    [cat:(X L t)][cat:(L)] cancel(SS.cat.2R)
 
 ST_F={([cat: (t)] rp_R5)}

Komplexität. LAG: C2 (polynomial): Die Regeln R1u und R2 weisen kompatible Eingabebedingungen auf. R1 referenziert die Regeln R1u und R2, somit entstehen bei dieser Grammatik Ambiguitäten. Da R1u die Regel R1 referenziert, ist die Ambiguität rekursiv. Da allerdings R1 nicht nach dem Ausführen von R2 nochmals aufgerufen werden kann, ist die entstandene Ambiguität lediglich “single return”. PSG: kontextsensitiv (exponentiell): Die Korrespondenz (ww ... w^R) ist weder binär noch invers.

L = a^kb^kc^k

Die Sprache L beinhaltet alle Wörter, die

• mit einer beliebigen Anzahl an Segmenten a beginnen, gefolgt von
• derselben Anzahl an Segmenten b, gefolgt von
• derselben Anzahl an Segmenten c.

Idee. Man speichert für jedes Segment a den Kategoriewert a in der Kategoriesequenz des Satzanfangs. Anschließend entfernt man für jedes Segment b den Wert am linken Rand der Kategoriesequenz und speichert den Wert b am rechten Rand. Schließlich entfernt man für jedes Segment c den Wert am linken Rand der Kategoriesequenz.

Algorithmus.

• [STS] Beginne mit einem Segment a und der Regel R1.
• [R1 ] Speichere für jedes Segment a einen entsprechenden Kategoriewert am rechten Rand der Kategoriesequenz des Satzanfangs. Fahre mit Regel R1 und R2 fort.
• [R2 ] Stelle für jedes Segment b sicher, dass der Wert am linken Rand der Kategoriesequenz des Satzanfangs a entspricht, entferne diesen Wert anschließend und speichere gleichzeitig für jedes Segment b einen entsprechenden Kategoriewert am rechten Rand. Fahre mit Regel R2 und R3 fort.
• [R3 ] Stelle für jedes Segment c sicher, dass der Wert am linken Rand der Kategoriesequenz des Satzanfangs b entspricht und entferne diesen Wert anschließend. Fahre mit Regel R3 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R3 beendet wurde und die Kategoriesequenz leer ist.

Skizze. Sei w=aaabbbccc ∈ L

 a.aabbbccc  R1:   (a)(a) => (aa) {R1,R2}
 aa.abbbccc  R1:  (aa)(a) => (aaa) {R1,R2}
 aaa.bbbccc  R2: (aaa)(b) => (aab) {R2,R3}
 aaab.bbccc  R2: (aab)(b) => (abb) {R2,R3}
 aaabb.bccc  R2: (abb)(b) => (bbb) {R2,R3}
 aaabbb.ccc  R3: (bbb)(c) => (bb)  {R3}
 aaabbbc.cc  R3:  (bb)(c) => (b)   {R3}
 aaabbbcc.c  R3:   (b)(c) => ()    {R3}

Code. Für die Segmente a, b und c werden Lexikoneinträge benötigt. 

 [sur:a, cat:(a)], [sur:b, cat:(b)], [sur:c, cat:(c)] 

 

 ST_S = {([cat: (a)] {R1 R2 R3})}
 
 R1 {R1 R2} [cat: (_)] [cat: (a)]    concat(NW.sur SS.sur)
                                     acopy(a SS.cat)
 R2 {R2 R3} [cat: (a _)] [cat: (b)]  concat(NW.sur SS.sur)
                                     acopy(b SS.cat) 
                                     cancel(SS.cat.1)
 R3 {R3}    [cat: (b _)] [cat: (c)]  concat(NW.sur SS.sur)
                                     cancel(SS.cat.1) 
 ST_F = {([cat: ()] rp_R3)}

Komplexität. LAG:C1 (linear): Es entstehen keine Ambiguitäten, da die Regeln inkompatible Eingabebedingungen aufweisen. PSG: kontextsensitiv (exponentiell): Die Korrespondenz ist nicht binär (k in a^kb^kc^k).

L = a^kb^kc^kd^k

Die Sprache L enthält alle Wörter, die

• mit einer beliebigen Anzahl an Segmenten a beginnen, gefolgt von
• derselben Anzahl an Segmenten b, gefolgt von
• derselben Anzahl an Segmenten c, gefolgt von
• derselben Anzahl an Segmenten d.

Idee. Das Vorgehen ist analog zu dem in a^kb^kc^k. Allerdings löscht man nicht für jedes Segment c einen Wert aus der Kategoriesequenz sondern ersetzt den Wert b mit dem Wert c. Schließlich löscht man für jedes Segment d einen Wert c aus der Kategoriesequenz und akzeptiert das Ergebnis als gültig, wenn die Kategoriesequenz leer ist.

Algorithmus.

• [STS] Beginne mit dem Segment a und der Regel R1.
• [R1 ] Speichere für jedes Segment a den Kategoriewert a in der Kategoriesequenz des Satzanfangs. Fahre mit Regel R1 und R2 fort.
• [R2 ] Stelle für jedes Segment b sicher, dass der Kategoriewert am linken Rand ein a ist und entferne diesen. Hänge am rechten Rand den Kategoriewert b an. Fahre mit Regel R2 und R3 fort.
• [R3 ] Stelle für jedes Segment c sicher, dass der Kategoriewert am linken Rand ein b ist und entferne diesen. Hänge am rechten Rand den Kategoriewert c an. Fahre mit Regel R3 und R4 fort.
• [R4 ] Stelle für jedes Segment d sicher, dass der Kategoriewert am linken Rand ein c ist und entferne diesen. Fahre mit Regel R4 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von R4 beendet wurde und die Kategoriesequenz leer ist.

Code. Für die Segmente a, b, c und d werden Lexikoneinträge benötigt.

 [sur:a, cat:(a)][sur:b, cat:(b)][sur:c, cat:(c)][sur:d, cat:(d)]

 
 ST_S = {([cat: (a)] {R1})}
 
 R1 {R1 R2} [cat: (_)] [cat: (a)]    concat(NW.sur SS.sur)
                                     acopy(a SS.cat)
 R2 {R2 R3} [cat: (a _)] [cat: (b)]  concat(NW.sur SS.sur)
                                     acopy(b SS.cat) 
                                     cancel(SS.cat.1)
 R3 {R3 R4} [cat: (b _)] [cat: (c)]  concat(NW.sur SS.sur)
                                     acopy(b SS.cat) 
                                     cancel(SS.cat.1)
 R4 {R4}    [cat: (c _)] [cat: (d)]  concat(NW.sur SS.sur)
                                     cancel(SS.cat.1) 
 
 ST_F = {([cat: ()] rp_R4)}

Komplexität. LAG: C1 (linear): Es entstehen keine Ambiguitäten, da die Regeln inkompatible Eingabebedingungen aufweisen. PSG: kontextsensitiv (exponentiell): Die Korrespondenz ist nicht binär (k in a^kb^kc^kd^k).

L = a²^i

Die Sprache L beinhaltet alle Wörter, die aus mehreren Segmenten a bestehen, wobei die Anzahl der Segmente 2ⁿ entspricht, z.B. a, aa, aaaa, aaaaaaaa, etc.

Idee. Man kann 2ⁿ inkrementell berechnen, indem der vorherige Wert stetig verdoppelt wird. Das kann durch das Hinzufügen des Werts selbst realisiert werden. 

               (a)
   1 + 1 = 2   (bb)
   2 + 2 = 4   (aaaa)
   4 + 4 = 8   (bbbbbbbb)
   8 + 8 = 16  (aaaaaaaaaaaaaaaa)
 
   2+2=4: (bb)-a->(baa)-a->(aaaa) 

Der Wert 1 wird mit einer Kategoriesequenz der Länge 1 dargestellt, der Wert 2 mit einer Kategoriesequenz der Länge 2 und der Wert 2ⁿ mit einer Kategoriesequenz der Länge 2ⁿ. Die Addition wird mit Hilfe des Shiftens der Kategoriesequenz modelliert. Dabei ersetzt man die geshifteten Werte mit zwei unterschiedlichen Werten, damit erkennbar ist, wann alle Elemente einmal komplett durchgeshiftet wurden. Durch das Ersetzen wird ebenfalls sichergestellt, dass sich die Länge der Kategoriesequenz nach einem erfolgreichen Shiftvorgang verdoppelt hat.

Algorithmus. Es werden lediglich zwei Regeln benötigt, Ra2b und Rb2a.

• [STS] Stelle sicher, dass das erste Segment ein a mit der Kategoriesequenz (a) ist. Beginne mit der Regel Ra2b.
• [Ra2b] Stelle sicher, dass das nächste Segment ein a ist. Entferne den Wert a am linken Rand der Kategoriesequenz des Satzanfangs und hänge zwei Werte b am rechten Rand an. Fahre mit Regel Ra2b und Rb2a fort.
• [Rb2a] Stelle sicher, dass das nächste Segment ein a ist. Entferne den Wert b am linken Rand der Kategoriesequenz des Satzanfangs und hänge zwei Werte a am rechten Rand an. Fahre mit Regel Ra2b und Rb2a fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung von Ra2b oder Rb2a beendet wurde und die Kategoriesequenz mit dem identischen Wert a oder b beginnt und endet.

Skizze. Sei w=aaaaaaaa ∈ L

 a.aaaaaaa  Ra2b:       (a)(a) => (bb)      {Ra2b,Rb2a}
 aa.aaaaaa  Rb2a:      (bb)(a) => (baa)     {Ra2b,Rb2a}
 aaa.aaaaa  Rb2a:     (baa)(a) => (aaaa)    {Ra2b,Rb2a}
 aaaa.aaaa  Ra2b:    (aaaa)(a) => (aaabb)   {Ra2b,Rb2a}
 aaaaa.aaa  Ra2b:   (aaabb)(a) => (aabbbb)  {Ra2b,Rb2a}
 aaaaaa.aa  Ra2b:  (aabbbb)(a) => (abbbbbb) {Ra2b,Rb2a}
 aaaaaaa.a  Ra2b: (abbbbbb)(a) => (bbbbbbbb){Ra2b,Rb2a} 

Code. Das Wort ist Teil der Sprache L, da die Kategorie nur aus a und b besteht.

 [sur:a, cat:(a)]

 
 ST_S = {([cat: (a)] {Ra2b})}
 
 Ra2b {Ra2b,Rb2a} [cat: (a _)][cat: (a)]  concat(NW.sur SS.sur)
                                          cancel(SS.cat.1)
                                          acopy(b b SS.cat)
 Rb2a {Ra2b,Rb2a} [cat: (b _)][cat: (a)]  concat(NW.sur SS.sur)
                                          cancel(SS.cat.1)
                                          acopy(a a SS.cat)
 
 ST_F = {([cat: (a _ a)] rp_Rb2a) ,([cat: (b _ b)] rp_Ra2b)}

Komplexität. LAG: C1 (linear): Es entstehen keine Ambiguitäten, da die Regeln inkompatible Eingabebedingungen aufweisen. PSG: kontextsensitiv (exponentiell), Pumping-Lemma.

L = a^∑ i

Die Sprache L beinhaltet alle Wörter, die aus Segmenten von a bestehen, wobei die Anzahl der Segmente im Wertebereich der Funktion f(x)=∑_i^x i liegt, z.B. a, aaa, aaaaaa, aaaaaaaaaa, etc.

Idee. Man geht rekursiv vor. Zunächst wird der entsprechende zweite Summand mittels der Kategoriesequenz des Satzanfangs gespeichert. Nach jedem Rekursionsschritt wird der zweite Summand inkrementiert. 

 1 + 2 = 3      
   + 3 = 6      
   + 4 = 10     
   + 5 = 15  

Die Anzahl der Elemente entspricht der Zahl, die hinzugefügt wird. Es werden zwei verschiedene Kategoriewerte verwendet, a und b. Dadurch kann festgestellt werden, wann alle Werte der Liste geshiftet wurden. Dafür verwendet man die Sequenzen (b a), (b b a), (b b b a). Diese geben an, dass der zweite Summand 2, 3, 4, etc. beträgt. Die Addition wird mit Hilfe des Shiftens der Kategoriesequenz des Satzanfangs simuliert. Für jedes kombinierte Segmente wird die Liste geshiftet, z.B.

 (b b b a)(a) => (b b a b)
 (b b a b)(a) => (b a b b)
 (b a b b)(a) => (a b b b) 

Ein möglicher Endzustand ist dann erreicht, wenn der Wert am linken Kategorierand ein a ist. Ist das der Fall, wird ein b am Ende angehängt, bevor die Kategoriesequenz weiter geshiftet wird.

 (a  b b b)(a) => (b b b  b  a)

Algorithmus. Der Algorithmus ist verhältnismäßig einfach. Es werden zwei Regeln benötigt: eine für die Addition des zweiten Summanden und eine für das Erhöhen und Zurücksetzen des zweiten Summanden.

• [STS] Stelle sicher, dass das erste Segment ein a ist. Fahre mit der Regel R2 fort.
• [R1] Stelle sicher, dass das nächste Segment ein a ist und dass der Wert am linken Rand der Kategoriesequenz des Satzanfangs ein b ist. Shifte die Kategoriesequenz und fahre mit Regel R1 und R2 fort.
• [R2] Stelle sicher, dass das nächste Segment ein a ist und dass der Wert am linken Rand der Kategoriesequenz des Satzanfangs ein b ist. Hänge ein b am Ende der Kategoriesequenz an. Shifte die Kategoriesequenz und fahre mit Regel R2 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung der Regel R2 beendet wurde.

Skizze. Sei w =aaaaaaaaaa ∈ L

 a.aaaaaaaaa  R1:       (a)(a) => (b a)      {R1}        
 aa.aaaaaaaa  R1:     (b a)(a) => (a b)      {R1}        (3)
 aaa.aaaaaaa  R1:     (a b)(a) => (b b a)    {R1}        
 aaaa.aaaaaa  R1:   (b b a)(a) => (b a b)    {R1}      
 aaaaa.aaaaa  R1:   (b a b)(a) => (a b b)    {R1}        (6)
 aaaaaa.aaaa  R1:   (a b b)(a) => (b b b a)  {R1}       
 aaaaaaa.aaa  R1: (b b b a)(a) => (b b a b)  {R1}        
 aaaaaaaa.aa  R1: (b b a b)(a) => (b a b b)  {R1}        
 aaaaaaaaa.a  R1: (b a b b)(a) => (a b b b)  {R1}        (10)

Code. Es wird lediglich ein Lexikoneintrag für a benötigt.

 [sur:a, cat:(a)] 

Da entweder R1 oder R2 ausgeführt wird, aber niemals beide gleichzeitig, kann man diese als Klauseln einer einzelnen Regel realisieren.

 ST_S = {([cat: (a)] {R1})}
 
 R1 {R1} [cat: (b _)][cat: (a)]  concat(NW.sur SS.sur)
                                 acopy(SS.cat.1 SS.cat)
                                 cancel(SS.cat.1)
         [cat: (a _)][cat: (a)]  concat(NW.sur SS.sur)
                                 acopy(b SS.cat.1 SS.cat)
                                 cancel(SS.cat.1)
 
 ST_F = {([cat: (a _)] rp_R1, rp_ST_S.1)}

Komplexität. LAG: C1-LAG (linear). Es entstehen keine Ambiguitäten, da die Regeln inkompatible Eingabebedingungen aufweisen. PSG: kontextsensitiv (exponentiell), Pumping-Lemma.

L = aⁿ²

Die Sprache L enthält alle Wörter, die aus Segmenten von a bestehen, wobei deren Anzahl einer Quadratzahl entspricht, z.B. a, aaaa, aaaaaaaaa,
aaaaaaaaaaaaaaaa, etc.

Idee. Die Sequenz aller Quadratzahlen kann durch simple Addition errechnet werden:

   1 +  3 =  4
   4 +  5 =  9
   9 +  7 = 16
  16 +  9 = 25
  25 + 11 = 36
  36 + 13 = 49
  49 + 15 = 64
  ... 

Die Addition von 3, 5, 7, ... wird durch das Shiften einer Liste von 3, 5, 7, ... Elementen inklusive eines Trennelements simuliert. Die erste Quadratzahl ist die Eins. Also beginnt man mit einer Liste der Länge eins, die nur das Trennelement enthält. Falls die Eingabe nur aus einem einzelnen a besteht, wird kein Kombinationsschritt ausgeführt. Das bedeutet, dass die Liste unverändert bleibt und das Trennsymbol nach wie vor erstes Element der Liste ist. Dies zeigt an, dass eine quadratische Anzahl von a eingelesen wurde. Falls mehr als ein a eingelesen wird, so werden zwei Elemente an die Liste angehängt und diese geshiftet. Für jedes weitere a wird die Liste erneut geshiftet. Dementsprechend wird das Trennzeichen nach drei weiteren Shifts wieder das erste Element der Liste sein und dadurch erneut signalisieren, dass eine quadratische Anzahl an a eingelesen wurde. Sollten weitere a folgen, werden wieder zwei Elemente hinzugefügt und erneut geshiftet.

Algorithmus.

• [STS] Stelle sicher, dass das erste Segment ein a ist. Beginne mit Regel R2.
• [R1] Stelle sicher, dass das nächste Segment ein a ist und dass der Wert am linken Rand der Kategoriesequenz des Satzanfangs ein b ist. Shifte die Kategoriesequenz und fahre mit Regel R1 und R2 fort.
• [R2] Stelle sicher, dass das nächste Segment ein a ist und dass der Wert am linken Rand der Kategoriesequenz des Satzanfangs ein b ist. Hänge zwei b am Ende der Kategoriesequenz an. Shifte die Kategoriesequenz und fahre mit Regel R2 fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung der Regel R2 beendet wurde.

Skizze. Sei w=aaaaaaaaa ∈ L

 a.aaaaaaaa  R1:          (a)(a)   => (b b a)        {R2}         
 aa.aaaaaaa  R2:      (b b a)(a)   => (b a b)        {R1,R2}      
 aaa.aaaaaa  R2:      (b a b)(a)   => (a b b)        {R1,R2}      
 aaaa.aaaaa  R1:      (a a b)(a)   => (b b b b a)    {R2}         
 aaaaa.aaaa  R2:  (b b b b a)(a)   => (b b b a b)    {R1,R2}      
 aaaaaa.aaa  R2:  (b b b a b)(a)   => (b b a b b)    {R1,R2}      
 aaaaaaa.aa  R2:  (b b a b b)(a)   => (b a b b b)    {R1,R2}      
 aaaaaaaa.a  R2:  (b a b b b)(a)   => (a b b b b)    {R1,R2}   

Code. Es wird lediglich ein Lexikoneintrag für das Segment a benötigt.

 [sur:a, cat:(a)] 

Da entweder R1 oder R2 ausgeführt wird, aber niemals beide gleichzeitig, kann man diese als Klauseln einer einzelnen Regel realisieren.

 ST_S = {([cat: (a)], {R1})}
 
 R1 {R1}    [cat: (a _)] [cat: (a)] concat(NW.sur SS.sur)
                                    acopy(b b a SS.cat)
                                    cancel(SS.cat.1L)
            [cat: (b _)] [cat: (a)] concat(NW.sur SS.sur)
                                    acopy(b SS.cat)
                                    cancel(SS.cat.1L)
 
 ST_F = {([cat: (a _)] rp_R1)}

Komplexität. LAG: C1 (linear): Es entstehen keine Ambiguitäten, da die Regeln inkompatible Eingabebedingungen aufweisen. PSG: kontextsensitiv (exponentiell), Pumping-Lemma. Die Einfachheit einer Grammatik hängt zu einem großen Teil von der Wahl des Algorithmus ab. Deshalb sollte der Programmierer zu allererst einen geeigneten Algorithmus wählen und erst danach darüber nachdenken, wie die Regeln dazu auszusehen haben.

L_minus

Die Sprache L__minus kann zur Simulation der Subtraktion verwendet werden und dient als Verständnishilfe für die Grammatik der Sprache subsetsum.

Idee. Die beiden Segmente “0” und “1” dienen zur Darstellung von Binärzahlen, das Segment “t” wird als Trenner verwendet, um den Beginn des Subtrahenden zu markieren und das Trennsegment “r” markiert den Anfang des Ergebnisses. Ein Wort besteht aus dem Minuenden, gefolgt von einer beliebigen Anzahl von Subtrahenden, gefolgt vom Ergebnis der Subtraktion.

z_minuend t z_{subtrahend_1} t . . . t z_{subtrahend_n} r z_result

Um das Parsing zu erleichtern, beginnen alle Ziffern mit den niedrigeren Bits.

29 = 1 * 16 + 1 * 8 + 1 * 4 + 0 * 2 + 1 * 1 = 11101₍₂₎ → 10111_(be)

Dies ist notwendig (zumindest für Subtrahenden), da die Subtraktion für gewöhnlich von rechts nach links durchgeführt wird. Um die Subtraktion von drei von vierzehn zu simulieren, bestimmt man die Binärdarstellung der Zahlen und kodiert die Bits des Minuenden, des Subtrahenden und des Ergebnisses in umgekehrter Reihenfolge:

14 - 3 = 1 * 8 + 1 * 4 + 1 * 2 + 0 * 1 - (1 * 2 + 1 * 1) = 1110₍₂₎ - 0011₍₂₎ = 1011₍₂₎

    0111         t         1100             r      1101minuend(be)         subtrahend(be)          result(be)

Aus Gründen der Einfachheit wird an dieser Stelle nur die Subtraktion mit einem Subtrahenden betrachtet. Ein Wort ist Teil der Sprache L, dann und nur dann, wenn Minuend - Subtrahend = Ergebnis. Die Subtraktion mit mehr als einem Subtrahenden kann durch wiederholte Subtraktion mit einem Subtrahenden modelliert werden. Die Subtraktion wird Bit für Bit durchgeführt. Es wird mit dem niedrigsten Bit begonnen, möglicher Übertrag auf den nächsten Subtraktionsschritt übertragen.

0 - 1	= 1	| Carry = 1
1 - 1 - Carry	= 0	| Carry = 0
1 - 0 - Carry	= 0	| Carry = 0
1 - 0 - Carry	= 1	| Carry = 0

Wenn nun die Ergebnisspalte von unten nach oben gelesen wird, erhält man folgendes Resultat:

1110₍₂₎ - 0011₍₂₎ = 1011₍₂₎

Wenn zwei Bits b₁ und b₂ subtrahiert werden, können die folgenden sechs Fälle unterschieden werden:

Carry = 0 ∧ b1 = b2            (R3)
Carry = 0 ∧ b1 = 0 ∧ b2 = 1 (R4)
Carry = 0 ∧ b1 = 1 ∧ b2 = 0 (R5)
Carry = 1 ∧ b1 = b2            (R7)
Carry = 1 ∧ b1 = 1 ∧ b2 = 0 (R8)
Carry = 1 ∧ b1 = 0 ∧ b2 = 1 (R9)

Algorithmus. Es werden elf Regeln benötigt: eine Regel für das Parsen des Minuenden (R1), eine Regel für das folgende Trennsymbol (R2), drei Regeln für die Subtraktion bei nicht gesetztem Übertragsbit (R3, R4, R5), drei Regeln für die Subtraktion bei gesetztem Übertragsbit (R7, R8, R9), eine Regel für das Trennsymbol, das den Anfang des Subtrahenden markiert (R6), eine Regel für das Trennsymbol, das den Anfang des Ergebnisses markiert (Rr) und eine Regel für das Überprüfen des Ergebnisses (Rc).

• [STS] Stelle sicher, dass das erste Segment entweder 0 oder 1 ist. Beginne mit Regel R1 und R2.
• [R1] Stelle sicher, dass der Kategoriewert des nächsten Segments 0 oder 1 ist. Speichere das entsprechende Segment am rechten Rand der Kategoriesequenz. Fahre mit Regel R1 und R2 fort.
• [R2] Stelle sicher, dass das nächste Segment das Trennsymbol ist. Speichere das Trennsymbol am linken Rand der Kategoriesequenz und fahre mit Regel R3, R4 und R5 fort.
• [R3] Die Regel R3 wird angewendet, wenn das Übertragsbit null ist und der Kategoriewert des nächsten Segments 0 oder 1 entspricht und mit dem Wert am linken Rand der Kategoriesequenz übereinstimmt. In diesem Fall ist das Ergebnis der Subtraktion null. Entferne also den Wert am linken Rand und füge 0 am linken Rand hinzu. Fahre mit den Regeln R3, R4, R5, R6 und Rr fort.
• [R4] Die Regel R4 wird angewendet, wenn das Übertragsbit null ist, der Kategoriewert des nächsten Segments 0 entspricht und der Wert am linken Rand der Kategoriesequenz 1 beträgt. In diesem Fall ist das Ergebnis der Subtraktion eins. Entferne also den Wert am linken Rand und füge 1 am rechten Rand hinzu. Fahre mit den Regeln R3, R4, R5, R6 und Rr fort.
• [R5] Die Regel R5 wird angewendet, wenn das Übertragsbit null ist, der Kategoriewert des nächsten Segments 1 entspricht und der Wert am linken Rand der Kategoriesequenz 0 beträgt. In diesem Fall ist das Ergebnis der Subtraktion eins und das Übertragsbit wird gesetzt. Entferne also den Wert am linken Rand und füge 1 am rechten Rand hinzu. Fahre mit den Regeln R7, R8 und R9 fort.
• [R6] Stelle sicher, dass das nächste Segment und der Wert am linken Rand der Kategoriesequenz ein Trenner ist. Shifte den Trenner. Fahre mit Regel R3, R4, R5, R6 und Rr fort.
• [R7] Die Regel R7 wird angewendet, wenn das Übertragsbit gesetzt ist und der Kategoriewert des nächsten Segments 0 oder 1 entspricht und mit dem Wert am linken Rand der Kategoriesequenz übereinstimmt. In diesem Fall ist das Ergebnis der Subtraktion eins und das Übertragsbit bleibt gesetzt. Entferne also den Wert am linken Rand und füge 1 am rechten Rand hinzu. Fahre mit den Regeln R7, R8 und R9 fort.
• [R8] Die Regel R8 wird angewendet, wenn das Übertragsbit gesetzt ist, der Kategoriewert des nächsten Segments 0 entspricht und der Wert am linken Rand der Kategoriesequenz 0 beträgt. In diesem Fall ist das Ergebnis der Subtraktion null und das Übertragsbit wird zurückgesetzt. Entferne also den Wert am linken Rand und füge 0 am rechten Rand hinzu. Fahre mit den Regeln R3, R4, R5, R6 und Rr fort.
• [R9] Die Regel R9 wird angewendet, wenn das Übertragsbit gesetzt ist, der Kategoriewert des nächsten Segments 1 entspricht und der Wert am linken Rand der Kategoriesequenz 0 beträgt. In diesem Fall ist das Ergebnis der Subtraktion eins und das Übertragsbit bleibt gesetzt. Entferne also den Wert am linken Rand und füge 1 am rechten Rand hinzu. Fahre mit den Regeln R7, R8 und R9 fort.
• [Rr] Stelle sicher, dass das nächste Segment der Marker für den Anfang des Ergebnisses ist und dass das Symbol am linken Rand der Kategoriesequenz das Trennsymbol ist. Entferne das Trennsymbol und fahre mit Regel Rc fort.
• [Rc] Stelle sicher, dass der Kategoriewert des nächsten Segments 0 oder 1 ist und dem Wert am linken Rand der Kategoriesequenz entspricht. Entferne diesen Wert am linken Rand und fahre mit Regel Rc fort.
• [STF] Akzeptiere das Ergebnis als gültig, wenn die Ableitung mit der Ausführung der Regel R6 beendet wurde und die Kategoriesequenz leer ist.

Skizze. Sei w=0111t1100t1101t ∈ L

 0.111t1100r1101  R1:         (0)(1) =>       (0 1)   {R1, R2}           
 01.11t1100r1101  R1:       (0 1)(1) =>     (0 1 1)   {R1, R2}           
 011.1t1100r1101  R1:     (0 1 1)(1) =>   (0 1 1 1)   {R1, R2}           
 0111.t1100r1101  R2:   (0 1 1 1)(t) => (0 1 1 1 t)   {R3, R4, R5, R6, Rr}   
 0111t.1100r1101  R5: (0 1 1 1 t)(1) => (1 1 1 t 1)   {R7,R8,R9}
 0111t1.100r1101  R7: (1 1 1 t 1)(1) => (1 1 t 1 1)   {R7,R8,R9}
 0111t11.00r1101  R8: (1 1 t 1 0)(0) => (1 t 1 1 0)   {R3, R4, R5, R6, Rr} 
 0111t110.0r1101  R4: (1 t 1 0 0)(0) => (t 1 1 0 1)   {R3, R4, R5, R6, Rr}  
 0111t1100.r1101  Rr: (t 1 1 0 1)(r) => (1 1 0 1)     {Rc} 
 0111t1100r.1101  Rc:   (1 1 0 1)(1) => (1 0 1)       {Rc} 
 0111t1100r1.101  Rc:     (1 0 1)(1) => (0 1)         {Rc} 
 0111t1100r11.01  Rc:       (0 1)(0) => (1)           {Rc} 
 0111t1100r110.1  Rc:         (1)(1) => ()            {Rc}

Code. Es werden Lexikoneinträge für die Segmente 0, 1 und t benötigt.

 [sur:"0", cat:("0")], [sur:"1", cat:("1")], [sur:t, cat:(t)] 

Sei B eine Variable mit den möglichen Werten 0 und 1.

 
 ST_S = {([cat: (B)], {R1 R2})}
 
 R1 {R1 R2} [cat: (_)] [cat: (B)]                  concat(NW.sur SS.sur)
                                                   acopy(B SS.cat)
 R2 {R3 R4 R5} [cat: (_)] [cat: (t)]               concat(NW.sur SS.sur)
                                                   acopy(t SS.cat)
 R3 {R3 R4 R5 R6 Rr} [cat: (B _)] [cat: (B)]       concat(NW.sur SS.sur)
                                                   cancel(SS.cat.1)
                                                   acopy("0" SS.cat 1)
 R4 {R3 R4 R5 R6 Rr} [cat: ("1" _)][cat: ("0")]    concat(NW.sur SS.sur)
                                                   cancel(SS.cat.1)
                                                   acopy("1" SS.cat)
 R5 {R7 R8 R9} [cat: ("0" _)] [cat: ("1")]         concat(NW.sur SS.sur)
                                                   cancel(SS.cat.1)
                                                   acopy("1" SS.cat)
 R6 {R3 R4 R5 R6} [cat: (t _)] [cat: (t)]          concat(NW.sur SS.sur)
                                                   cancel(SS.cat.1)
                                                   acopy(t SS.cat)
 R7 {R7 R8 R9} [cat: (B _)] [cat: (B)]             concat(NW.sur SS.sur)
                                                   cancel(SS.cat.1)
                                                   acopy("1" SS.cat)
 R8 {R3 R4 R5 R6 Rr} [cat: ("1" _)] [cat: ("0")]   concat(NW.sur SS.sur)
                                                   cancel(SS.cat.1)
                                                   acopy("0" SS.cat)
 R9 {R6 R7 R8}    [cat: ("0" _)] [cat: ("1")]      concat(NW.sur SS.sur)
                                                   cancel(SS.cat.1)
                                                   acopy("0" SS.cat)
 Rr {Rc}          [cat: (t _)] [cat: (r)]          concat(NW.sur SS.sur)
                                                   cancel(SS.cat.1)
 Rc {Rc}          [cat: (B _)] [cat: (B)]          concat(NW.sur SS.sur)
                                                   cancel(SS.cat.1)
                                                 
 ST_F = {([cat: ()] rp_Rc)}

Komplexität. LAG: C1 (linear): Es entstehen keine Ambiguitäten, da die Regeln inkompatible Eingabebedingungen aufweisen. PSG: kontextsensitiv (exponentiell): Die Korrespondenz ist nicht binär invers (Übertragsbit).