CB-I im WS99/00

Blatt 4 mit Lösungen

Aufgabe 1

Schreiben Sie die folgenden, in LEX-Schreibweise angegebenen regulären Ausdrücke in die Notation der Vorlesung um.
  1. Das Schlüsselwort begin:
      begin
    	  
  2. Float-Zahlen in Exponentschreibweise, z. Bsp. '+123e-12'
      [\+-]?[0-9]+[eE](-?[0-9]+)?  
    

Lösung

  1. (b · (e · (g · (i · n))))
  2. Zu beachten war, das der Backslash (\) nur als sogenanntes Escape-Symbol verwendet wird, um dem + seine Sonderbedeutung zu nehmen. Ansonsten modulo Klammerfehlern:

    ((\+ + (- + eps)) · (((0·(1·(2·(3·(4·(5·(6·(7·(8·9))))))))) · ((0·(1·(2·(3·(4·(5·(6·(7·(8·9))))))))))*) · ((e + E) · (((- + eps) · ((0·(1·(2·(3·(4·(5·(6·(7·(8·9))))))))) · ((0·(1·(2·(3·(4·(5·(6·(7·(8·9))))))))))*)) + eps) )))

Aufgabe 2

Sei folgende Grammatik gegeben:
G = {S,A,B,W,R,K}, {a,e,l,k,m,r,t,p,s,u,w,z}, P, S)
mit P = { S::=ApeK|BR , A::=eps|As , B::=tWl W::=atze|aWe|eps , R::=wurm|ApeK , K::=eps|Kk }
  1. Beschreiben Sie die erzeugte Sprache in der bereits öfter verwendeten Mengenschreibweise. (Bsp: {an|n < 24})
  2. Geben Sie eine aequivalente eps-freie Grammatik an.
  3. Leiten Sie in der eps-freien Version das Wort 'tatzelspekk' durch bottom-up-Analyse ab.
    Hinweis: Nummerieren Sie die Regeln vorher geeignet. Ggf. ist es einfacher, ein bottom-up-Analyseprogramm dazu zu schreiben

Lösung:

  1. Der einfachste Ansatz ist der, für jedes Nichtterminal eine Einzelmenge aufzustellen, und die sich dann ergebenden Mengen dann entsprechend der rechten Seite einer Regel bei Alternativen (bei |) zu vereinigen bzw. bei Hintereinanderfolge zu konkatenieren. Sicher ergebenden rekursive Definitionsgleichungen muß man natürlich auflösen:

    M_K := { kn | n >= 0 }
    M_R := {wurm} U ( M_A·{pe}·M_K
    M_W := { am(atze)nem | 0<=n<=1, m>0}
    M_B := {t}·M_W·{l}
    M_A := { sn | n >= 0 }
    L(G)=M_S := ( M_A·pe·M_K) U (M_B·M_R)
  2. Kanonisches Vorgehen: Man markiert eine eps-Regel (z.Bsp. K::=eps). Dann geht man alle rechten Regelseiten durch. Tritt das entsprechende Nichtterminal (K) auf der rechten Seite auf (z.Bsp. R::=ApeK, muß zusätzlich noch diese Regel ohne das Nichtterminal aufgenommen werden (R::=Ape). Hat man alle rechten Seite betrachtet, kann die markierte eps-Produktion gelöscht werden. Insgesamt erhält man hier:
    G = {S,A,B,W,R,K}, {a,e,l,k,m,r,t,p,s,u,w,z}, P, S)
    mit P = { S::=peK|pe|Ape|ApeK|BR , A::=s|As , B::=tWl|tl , W::=atze|aWe|ae , R::=wurm|ApeK|Ape|peK|pe , K::=k|Kk }
  3. Ein wechelseitig rekurisver Algorithums zur nichtdeterministischen Bottom-Up-analyse (in Perl geschrieben) liefert die folgende Lösung. Bessere Ergebnisse kannman ggf. durch Umnummerierung der Regel erreichen.
    Regeln:
     0: S::=ApeK
     1: S::=Ape
     2: S::=peK
     3: S::=pe
     4: S::=BR
     5: A::=As
     6: A::=s
     7: B::=tWl
     8: B::=tl
     9: W::=atze
     10: W::=aWe
     11: W::=ae
     12: R::=wurm
     13: R::=ApeK
     14: R::=Ape
     15: R::=peK
     16: R::=pe
     17: K::=Kk
     18: K::=k
     
    Wort: tatzelspekk
    
    shift
    (t,atzelspekk): shift
    (ta,tzelspekk): shift
    (tat,zelspekk): shift
    (tatz,elspekk): shift
    (tatze,lspekk): reduce, Regel 9 (W::=atze)
    (tW,lspekk): shift
    (tWl,spekk): reduce, Regel 7 (B::=tWl)
    (B,spekk): shift
    (Bs,pekk): reduce, Regel 6 (A::=s)
    (BA,pekk): shift
    (BAp,ekk): shift
    (BApe,kk): reduce, Regel 1 (S::=Ape)
    (BS,kk): shift
    (BSk,k): reduce, Regel 18 (K::=k)
    (BSK,k): shift
    (BSKk,): reduce, Regel 17 (K::=Kk)
    (BSK,): back: shift
    back: Regel 17
    reduce, Regel 18 (K::=k)
    (BSKK,): back: shift
    back: Regel 18
    back: shift
    back: shift
    back: Regel 18
    shift
    (BSkk,): reduce, Regel 18 (K::=k)
    (BSkK,): back: shift
    back: Regel 18
    back: shift
    back: shift
    back: shift
    back: Regel 1
    reduce, Regel 3 (S::=pe)
    (BAS,kk): shift
    (BASk,k): reduce, Regel 18 (K::=k)
    (BASK,k): shift
    (BASKk,): reduce, Regel 17 (K::=Kk)
    (BASK,): back: shift
    back: Regel 17
    reduce, Regel 18 (K::=k)
    (BASKK,): back: shift
    back: Regel 18
    back: shift
    back: shift
    back: Regel 18
    shift
    (BASkk,): reduce, Regel 18 (K::=k)
    (BASkK,): back: shift
    back: Regel 18
    back: shift
    back: shift
    back: shift
    back: Regel 3
    reduce, Regel 14 (R::=Ape)
    (BR,kk): reduce, Regel 4 (S::=BR)
    (S,kk): shift
    (Sk,k): reduce, Regel 18 (K::=k)
    (SK,k): shift
    (SKk,): reduce, Regel 17 (K::=Kk)
    (SK,): back: shift
    back: Regel 17
    reduce, Regel 18 (K::=k)
    (SKK,): back: shift
    back: Regel 18
    back: shift
    back: shift
    back: Regel 18
    shift
    (Skk,): reduce, Regel 18 (K::=k)
    (SkK,): back: shift
    back: Regel 18
    back: shift
    back: shift
    back: shift
    back: Regel 4
    shift
    (BRk,k): reduce, Regel 18 (K::=k)
    (BRK,k): shift
    (BRKk,): reduce, Regel 17 (K::=Kk)
    (BRK,): back: shift
    back: Regel 17
    reduce, Regel 18 (K::=k)
    (BRKK,): back: shift
    back: Regel 18
    back: shift
    back: shift
    back: Regel 18
    shift
    (BRkk,): reduce, Regel 18 (K::=k)
    (BRkK,): back: shift
    back: Regel 18
    back: shift
    back: shift
    back: shift
    back: Regel 14
    reduce, Regel 16 (R::=pe)
    (BAR,kk): shift
    (BARk,k): reduce, Regel 18 (K::=k)
    (BARK,k): shift
    (BARKk,): reduce, Regel 17 (K::=Kk)
    (BARK,): back: shift
    back: Regel 17
    reduce, Regel 18 (K::=k)
    (BARKK,): back: shift
    back: Regel 18
    back: shift
    back: shift
    back: Regel 18
    shift
    (BARkk,): reduce, Regel 18 (K::=k)
    (BARkK,): back: shift
    back: Regel 18
    back: shift
    back: shift
    back: shift
    back: Regel 16
    shift
    (BApek,k): reduce, Regel 18 (K::=k)
    (BApeK,k): reduce, Regel 0 (S::=ApeK)
    (BS,k): shift
    (BSk,): reduce, Regel 18 (K::=k)
    (BSK,): back: shift
    back: Regel 18
    back: shift
    back: shift
    back: Regel 0
    reduce, Regel 2 (S::=peK)
    (BAS,k): shift
    (BASk,): reduce, Regel 18 (K::=k)
    (BASK,): back: shift
    back: Regel 18
    back: shift
    back: shift
    back: Regel 2
    reduce, Regel 13 (R::=ApeK)
    (BR,k): reduce, Regel 4 (S::=BR)
    (S,k): shift
    (Sk,): reduce, Regel 18 (K::=k)
    (SK,): back: shift
    back: Regel 18
    back: shift
    back: shift
    back: Regel 4
    shift
    (BRk,): reduce, Regel 18 (K::=k)
    (BRK,): back: shift
    back: Regel 18
    back: shift
    back: shift
    back: Regel 13
    reduce, Regel 15 (R::=peK)
    (BAR,k): shift
    (BARk,): reduce, Regel 18 (K::=k)
    (BARK,): back: shift
    back: Regel 18
    back: shift
    back: shift
    back: Regel 15
    shift
    (BApeKk,): reduce, Regel 17 (K::=Kk)
    (BApeK,): reduce, Regel 0 (S::=ApeK)
    (BS,): back: shift
    back: Regel 0
    reduce, Regel 2 (S::=peK)
    (BAS,): back: shift
    back: Regel 2
    reduce, Regel 13 (R::=ApeK)
    (BR,): reduce, Regel 4 (S::=BR)
    (S,): Wort tatzelspekk in L(G)
    
    	  

Aufgabe 3

Bestimmen Sie die von folgendem Kellerautomaten akzeptierte Sprache: K = ({p,q},{(,),a},{A,D},d,p,D,{q}), d gegeben durch
d(p,(,A)=(p,AA), d(p,),A)=(p,eps), d(p,a,A)=(p,A),
d(p,(,D)=(p,AD), d(p,eps,D)=(q,D), d(p,a,D)=(p,D)

Lösung

L(K) = {b* | b ist aus {a,(,)} und in jedem Element ist die Anzahl der ( gleich der Anzahl der ) }.
Beweisen würde man das wohl induktiv, etwa über die Wortlänge oder konkreter über die Anzahl von ) oder ( im Wort.

Dietmar Lammers
Last modified: Wed Nov 17 15:57:12 MET 1999