Lösung 07

Dateiinhalt

Musterloesung Blatt 7
---------------------


H-14:

Der PDA ist ({q},{0,1},{Z,P,N},delta,q,Z)
mit den Uebergaengen delta:

q |    Z     |    P     |    N     |
--+----------+----------+----------+
0 | {(q,PZ)} | {(q,PP)} | {(q,e)}  |
1 | {(q,NZ)} | {(q,e)}  | {(q,NN)} |
e | {(q,e)}  |          |          |
--+----------+----------+----------+

Idee: der String auf dem Stack repraesentiert |w|_0 - |w|_1, 
wobei P^nZ fuer +n und N^nZ fuer -n steht. 


H-15:

Der PDA ist ({q},{a,b,c},{a,b,c,S,A},delta,q,S) 
mit den Uebergaengen delta:

q |    a    |    b    |    c    |     S     |          A            |
--+---------+---------+---------+-----------+-----------------------+
a | {(q,e)} |         |         |           |                       |
b |         | {(q,e)} |         |           |                       | 
c |         |         | {(q,e)} |           |                       |
e |         |         |         | {(q,aAA)} | {(q,aS),(q,bS),(q,c)} |
--+---------+---------+---------+-----------+-----------------------+

Akzeptierende Berechnung bei abaccbacaacc

q  abaccbacaacc   S
q  abaccbacaacc   aAA
q   baccbacaacc   AA
q   baccbacaacc   bSA
q    accbacaacc	  SA
q    accbacaacc	  aAAA
q     ccbacaacc	  AAA
q     ccbacaacc	  cAA
q      cbacaacc	  AA
q      cbacaacc	  cA
q       bacaacc	  A
q       bacaacc	  bS
q        acaacc	  S
q        acaacc	  aAA
q         caacc	  AA
q         caacc   cA
q          aacc	  A
q          aacc	  aS
q           acc	  S
q           acc	  aAA
q            cc	  AA
q            cc	  cA
q             c	  A
q             c	  c
q             e	  e