Aufgabe 1

Zeigen Sie: Die deterministischen kontextfreien Sprachen sind nicht abgeschlossen gegenüber Schnittbildung

Lösung:

Ein direktes Gegenbeispiel ist
L1:={anbncm | n,m >= 0} (det. kontextfrei),
L2:={anbmcm | n,m >= 0} (det. kontextfrei) und
L1 geschnitten L2 ={ambmcm | m >= 0} ist nicht mal kontextfrei.

Aufgabe 2

(Gegenüber der ursprünglichen Aufgabe haben wir aus Konsistenzgründen die Nichtterminale S und B vertauscht, so dass S wieder Startsymbol ist)

Gegeben Sei die Grammatik G = { {S,D,B}, {p,q,(,),;}, P, S} mit P = { S::=(D;B), D::=D;p, D::=p, B::q;B B::=q }

1. Geben Sie die kanonische Kollektion J₁ für G an.
2. Berechnen Sie damit die Analyseaktions- und Sprungtabelle
3. Analysieren Sie mit Hilfe der Tabellen das Wort (p;p;q;q)

Lösung:

1. Wir nummerieren die Zustände, beginnend mit 0. In den Tabellen verzichten wir dann auf das führende "z". J1 besteht aus

   z0 = Ik(epsilon) = { [S-> . (D;B), ] },
   z1 = Ik(() = { [S->( . D;B), ], [D-> . D;p, ;], [D-> . p, ;] },
   z2 = Ik((D) = { [S->(D . ;B), ], [D->D . ;p, ;] },
   z3 = Ik((p) = { [D->p . , ;] },
   z4 = Ik((D;) = { [S->(D; . B), ], [D->D; . p, ;], [B-> . q;B, )], [B-> . q, )] },
   z5 = Ik((D;B) = { [S->(D;B . ), ] },
   z6 = Ik((D;p) = { [D->D;p . , ;] },
   z7 = Ik((D;q) = { [B->q . ;B, )], [B->q . , )] },
   z8 = Ik((D;B)) = { [S->(D;B) . , ] },
   z9 = Ik((D;q;) = { [B->q; . B, )], [B-> . q;B, )], [B-> . q, )] },
   z10 = Ik((D;q;B) = { [B->q;B . , )] },
   
   ( Ik((D;q;q = Ik((D;q) )
   	  

2. Wir geben der bvesseren Übersicht wegen auch das das jeweilige gamma mit an, und bei den shifts der Analyseaktionsfunktion auch den von der goto-Funktion gelieferten Folge-Kellerzustand.

   goto-Funktion

   g	(	)	;	p	q	S	D	B
   z0 - eps	1
   z1 - (				3			2
   z2 - (D			4
   z3 - (p
   z4 - (D;				6	7			5
   z5 - (D;B		8
   z6 - (D;p
   z7 - (D;q			9
   z8 - (D;B)
   z9 - (D;q;					7			10
   z10 - (D;q;B

   Analyseaktions-Funktion

   f	(	)	;	p	q	eps
   z0 - eps	s (1)
   z1 - (				s (3)
   z2 - (D			s (4)
   z3 - (p			D->p
   z4 - (D;				s (6)	s (7)
   z5 - (D;B		s (8)
   z6 - (D;p			D->D;p
   z7 - (D;q		B->q	s (9)
   z8 - (D;B)						S->(D;B)
   z9 - (D;q;					s (7)
   z10 - (D;q;B		B->q:B

3. Analyses des Wortes (p;p;q;q): Wir gegben jeweils den Keller, Lookahead und anzuwendenden Funktion mit Ergebniswert an:

   K=0, L=(, f(0,()=s
   K=0 ( , L=p, g(0,()=1
   K=0 ( 1, L=p, f(1,p)=s
   K=0 ( 1 p, L=; g(1,p)=3
   K=0 ( 1 p 3, L=; f(3,;)=D->p
   K=0 ( 1 D, L=; g(1,D)=2
   K=0 ( 1 D 2, L=; f(2,;)=s
   K=0 ( 1 D 2 ;, L=p, g(2,;)=4
   K=0 ( 1 D 2 ; 4, L=p, f(4,p)=s
   ... in der Folge immer einen goto- und einen Analyseschritt auf einmal ...
   K=0 ( 1 D 2 ; 4 p, L=; g(4,p)=6, f=(6,;)=D->D;p
   K=0 ( 1 D, L=; g(1,D)=2, f(2,;)=s
   K=0 ( 1 D 2 ;, L=q, g(2,;)=4, f(4,q)=s
   K=0 ( 1 D 2 ; 4 q, L=; g(4,q)=7, s(7,;)=s
   K=0 ( 1 D 2 ; 4 q 7 ;, L=q, g(7,;)=9; f(9,q)=s
   K=0 ( 1 D 2 ; 4 q 7 ; 9 q, L=), q(9,q)=7, f(7,))=B->q
   K=0 ( 1 D 2 ; 4 q 7 ; 9 B, L=), g(9,B)=10, f(10,))=B->q;B
   K=0 ( 1 D 2 ; 4 B, L=), g(4,B)=5, f(5,))=s
   K=0 ( 1 D 2 ; 4 B 5 ), L=eps, g(5,))=8, f(8,eps)=S->(D;B)
   K=0 S
   	  

   Das Wort liegt also in der Sprache, und anhand der Regelreihenfolge bei der Analyse ergibt sich folgende Ableitung:

   (    p   ;   p    ;   q   ;   q    )
   |    |   |   /    |   |   /   |    |
   |    D   /  /     /   |  /    B    |
   |    |  /  /     /    | /    /     /
   |    |  | /     /     |     /     /
   |    | / /     /      |    /     /
   |    |/ /     /       |   /     / 
   |    D       /         B       /
   \    |      /         /       /
    \   |     /         /_______/
     \  |    /         / 
      \ |   /_________/
       \\  /
         S