 Kellerautomat zu einer gegebenen Sprache |
NC10
Grünschnabel
Dabei seit: 28.06.2011
Beiträge: 1
 |
|
| Kellerautomat zu einer gegebenen Sprache |
     |
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
|
|
28.06.2011 23:49 |
|
|
genieNot
unregistriert
|
|
Also spontan kommt mir folgende Idee:
Halte zunächst einmal alle Menge disjunkt, sonst verwirrt man sich nur selbst. Versuch mal jetzt alles zu vereinigen. Was spannend bleibt ist wohl die Überführungsrelation. Als Startzustand führe man einen eigenen ein, z.B.: S . Nun führe man folgende Regel ein: S -> Startzustand vom ersten Automaten, S -> Startzustand vom zweiten Automaten.
Ich meine das sollte klappen. Am besten macht man sich nun klar, was für ein beliebiges wort x gilt.
|
|
|
30.06.2011 21:35 |
|
|
genieNot
unregistriert
|
|
Deine Sorge um den Stack (Keller) ist berechtigt. Bedenke das Kelleralphabet kann beliebig gewählt werden, es steht nur symbolisch für etwas. Wie schon gesagt, wenn du die Kelleralphabete disjunkt hälst, dann hast du das Problem doch gar nicht mehr.
|
|
|
30.06.2011 21:37 |
|
|
|
