|
|
Meine Frage:
Hallo,
ich sitze schon seit einiger Zeit an folgender Aufgabe:
Geben sie einen Kellerautomaten für folgende Sprache an:
{a^nb^n|n>=0} U {a^nb^(2n)|n>=0}
wobei das U für Vereinigung steht.
(Also die Sprache, die aaa...bbb... liest genauso viele a's wie auch b's vereinigt mit der Sprache, die aaa...bbbbbb...., wobei doppelte so viele b's wie a's.)
Meine Ideen:
Mein Ansatz:
1. Ich habe einen Automaten für die erste der beiden Sprache der Vereinigung konstruiert: {a^nb^n|n>=0}
M1=({z0,z1,z2}, {a,b}, {#,a}, delta, z0, #)
delta(z0,a,#)={z0,a#}
delta(z0,a,a)={z0,aa}
delta(z0,b,a)={z1,epsilon}
delta(z1,b,a)={z1,epsilon}
delta(z1,epsilon,#)={z2,epsilon}
2. Ich habe eine Kellerautomaten für die zweite der beiden Sprachen konstruiert: {a^nb^(2n)|n>=0}
M2=({z0,z1,z2}, {a,b}, {#,a}, delta, z0, #)
Dabei habe ich mir gedacht, dass er ja eigentlich so ähnlich aussehen muss wie oben. Meine Überlegung war, dass wenn ich ein a lese, zwei a's auf den Keller lege. Sobald ein b gelesen wird wird dann ein a vom keller genommen, aber nur ein a. Somit habe ich am Ende doppelt soviele b's wie a's.
delta(z0,a,#)={z0,aa#}
delta(z0,a,a)={z0,aaaa}
delta(z0,b,a)={z1,epsilon}
delta(z1,b,a)={z1,epsilon}
delta(z1,epsilon,#)={z2,epsilon}
Jetzt zu meiner Frage: Wie bekomme ich jetzt die Vereinigung der beiden Sprachen zusammen?
Ich glaube einfach all meine delta- Funktionen zusammenwerfen geht nicht, sonst könne man ja vermischen und man legt manchmal beim lesen von a's dafür zwei a's in den Keller und manchmal eben nicht. Damit ist meine erwünschte Sprache nicht gewährleistet. Wie kann ich festlegen, dass entweder das eine oder das andere geschieht?
Ich hoffe das ist einigermaßen verständlich und ich bedanke mich schon mal im Vorraus.
Danke
NC10
|
|
