Vorlesung Übungsaufgabe gestellt am
Thümmel: Formale Syntax Vereinigung von L1 und L2 15. Jan. 1998
 
nächste Aufgabe, Übersicht und vorherige Aufgabe

Zielsetzung

Zu den gegebenen Sprachen L1 und L2 soll die Vereinigung gebildet und dazu ein Automat konstruiert werden, der genau diese Sprache akzeptiert. Anschließend wird versucht, eine Typ 3 Syntax aufzustellen.

Vereinigung der beiden Sprachen

Eine Syntax ist schnell aufgestellt, wenn man die Regeln S -> A und S -> B aufnimmt und dann aus A die Sätze von L1 und aus B die von L2 entwickelt:
Sprache Regeln der Syntax Syntax Typ
Vereinigung von L1 und L2: 
{ x | x = a b* a  oder  x Î {a, b}*  mit genau zwei b}		 S -> A 
S -> B 
A -> aCa 
C -> e 
C -> bC 
B -> aB 
B -> bD 
D -> aD 
D -> bE 
E -> aE 
E -> e		 Typ 1nr

Konstruktion eines Automaten

Auch ein Automat, der genau die Vereinigung der beiden Sprachen L1 und L2 akzeptiert, kann konstruiert werden, ohne die Vereinigung zu vereinfachen. Ich baue die Übergänge erstmal für L1 und protokolliere mit den Zuständen q0 bis q5, wieviele b bereits eingelesen wurden (nur bis 3). Wird ein Zeichen gelesen, das nicht zu L1 paßt, springt mein Automat in einen Zustand, der für L2 steht und natürlich auch die Anzahl der gelesenden b kodiert:
 
K {q0, q1, q2, q3, q4, q5, q6, q7, q8} Zustände
V {a, b} Eingabesymbole
S {q0} Startzustände
F {q5, q8} Endzustände
d (q0, a) -> (q1) 
(q1, b) -> (q2) 
(q2, b) -> (q3) 
(q3, b) -> (q4) 
(q4, b) -> (q4) 
(q4, a) -> (q5) 

(q0, b) -> (q7) 
(q7, a) -> (q7) 
(q7, b) -> (q8) 
(q8, a) -> (q8) 

(q6, a) -> (q6) 
(q6, b) -> (q7) 

(q1, a) -> (q6) 
(q2, a) -> (q7) 
(q3, a) -> (q8)

 Übergangsfunktion
 
Graphik:
 
Wieso ist q4 notwendig? Kann man die Wiederholte Eingabe von b nicht auch bei q3 anbauen? Schließlich sind q5 und q8 Endzustände.
Nein. Bei q8 werden noch weitere a verarbeitet. Eine Kette wie z.B. abbbaa darf aber nicht akzeptiert werden; dagegen sind abbaa und abbba erlaubt.

Konstruktion einer Syntax

Zu der Vereinigung zweier Sprachen kann man schnell eine Syntax aufstellen, wenn zu den beiden Sprachen jeweils eine Syntax gegeben ist.(Vergleiche dazu die eingangs aufgestellte Syntax.) Die Idee ist, gar nicht erst zu versuchen, irgendwelche Gemeinsamkeiten der beiden Sprachen zu suchen, und diese dann entsprechend in die Syntax einzubauen, sondern beide Regelmengen wie im folgenden zu verbinden:
Zuerst aber Syntaxen für L1 und L2:
L1 { x = ab*a } S -> aBa 
B -> e 
B -> bB		 Typ 1nr
L2 { x Î {a, b}* | b in x genau zwei mal enthalten} S -> aS 
S -> Sa 
S -> bB 
S -> Bb 
B -> aB 
B -> Ba 
B -> bC 
B -> Cb 
C -> aC 
C -> e		 Typ 0
L2 { x Î {a, b}* | b in x genau zwei mal enthalten} S -> aS 
S -> bB 
B -> aB 
B -> bC 
C -> aC 
C -> e		 Typ 0, da S Î y 
(sonst Typ 3
kontextfrei,
rechtslinear und
rechtsprädikativ)
L2 { x Î {a, b}* | b in x genau zwei mal enthalten} S -> AbAbA 
A -> e 
A -> aA
 
Das erste, etwas lange Regelwerk für die Sprache L2 lehnt sich an den Automaten an. Die zweite Syntax ist der Einleitung (s.o.) entnommen. Die dritte Syntax besitzt nur drei Regeln, hat dafür aber nicht mehr Normalform. Für die Syntax der Vereinigung der beiden Sprachen wähle ich zuerst die Regeln S -> A und S -> B. Aus A sollen dann alle Sätze von L1 abgeleitet werden können und aus B entsprechend die Sätzte von L2.
Sprache Regeln der Syntax Syntax Typ
Vereinigung von L1 und L2: 
{ x | x = a b* a  oder  x Î {a, b}*  mit genau zwei b}		 S -> A 
S -> B 
A -> aCa 
C -> e 
C -> bC 
B -> DbDbD 
D -> e 
D -> aD		 Typ 1nr

Joachim Wagner
Osnabrück, den 04. Februar 1998