Es sei ´G = ({S,B,U}, {a,b}, R, S)´ eine kontextfreie Grammatik mit
´R = {S -> BU, B -> aBa, B -> bBb, B -> lambda, U -> aUb, U -> lambda}´.
- Konstruiere einen Kellerautomaten ´M´, der ´L(G)´ akzeptiert
- Gib eine Linksableitung für ´aaab´ an
- Gib eine akzeptierende Berechnung des Kellerautomaten ´M´ für das Eingabewort ´aaab´ an
Teil 1
Im Keller werden die Satzformen (ohne den schon gelesenen Teil) gespeichert. Am Anfang ist ´S´ in den Keller zu schreiben und man geht in ´z_1´. In ´z_1´ erfolgt die Veränderung der Satzform, d.h. für eine Regel ´X -> w´ wird beim Kellerautomat ´(z_1, N, w)´ in ´delta(z_1, a, X)´ aufgenommen. Außerdem wird die Eingabe mit der Satzform verglichen, falls Terminale oben im Keller stehen.
Teil 2
Eine Linksableitung für ´aaab´ ist
´S => BU => aBaU => aaU => aaaUb => aaab´
Teil 3
Die zugehörige Berechnung von ´M´ ist
´(aaab, z_0, #) |-- ´´(aaab, z_1, S#) |-- (aaab, z_1, BU#) |-- ´´(aaab, z_1, aBaU#) |-- (aab, z_1, BaU#) |-- ´´(aab, z_1, aU#) |-- (ab, z_1, U#) |-- ´´(ab, z_1, aUb#) |-- (b, z_1, Ub#) |-- ´´(b, z_1, b#) |-- (lambda, z_1, #)´
Teil 1
´M = ({a,b}, {z_0, z_1, z_2}, {a,b,S,B,U}, z_0, {z_1}, delta)´
mit
´delta(z_0, a, #) = delta(z_0, b, #) = {(z_1, N, S)}´ ´delta(z_1, a, S) = delta(z_1, b, S) = {(z_1, N, BU)}´ ´delta(z_1, a, B) = delta(z_1, b, B) = {(z_1, N, aBa), (z_1, N, bBb), (z_1, N, lambda)}´ ´delta(z_1, a, U) = delta(z_1, b, U) = {(z_1, N, aUb), (z_1, N, lambda)}´ ´delta(z_1, a, a) = delta(z_1, b, b) = {(z_1, R, lambda)}´ ´delta(z_1, a, b) = delta(z_1, b, a) = {(z_2, R, lambda)}´ ´delta(z_2, x, y) = (z_2, N, y) " für alle " x in {a, b}, y in {a, b, S, B, U}´
Teil 2
´S => BU => aBaU => aaU => aaaUb => aaab´
Teil 3
´(aaab, z_0, #) |-- ´´(aaab, z_1, S#) |-- (aaab, z_1, BU#) |-- ´´(aaab, z_1, aBaU#) |-- (aab, z_1, BaU#) |-- ´´(aab, z_1, aU#) |-- (ab, z_1, U#) |-- ´´(ab, z_1, aUb#) |-- (b, z_1, Ub#) |-- ´´(b, z_1, b#) |-- (lambda, z_1, #)´
HPI, 2014-04-29, Theoretische Informatik 2, Blatt 4, Aufgabe 1
2014-07-21 23:00:21 UTC
2014-07-21 23:00:21 UTC