 Kellerautomat Verständnisfrage |
toobee
Grünschnabel
Dabei seit: 02.06.2008
Beiträge: 1
 |
|
| Kellerautomat Verständnisfrage |
     |
hi,
wir haben jetzt mit dem Thema Kellerautomaten angefangen, was ich dachte verstanden zu haben. Ein blick auf das übungsblatt hat das aber korrigiert.
Habe hier folgend eAufgabe:
Über ein Terminalalphabet E = {a,b,c} sie folgende Sprache gegeben:
L = {w | w = a^i b^i c^k mit i,k element IN}
dazu soll ich jetzt eine kontexfreie Grammatik angeben und einen Stapel-kellerautomaten konstruieren.
Nun scheitere ich aber schon an der gegebenen Sprache.
Ich muss ja soviele b's erzeugen wie ich a's hatte um diese alle aus dem keller rauszuholen. Aber was ist mit dem c^k ? wird da überhaupt was in den keller gelegt? ich versteh irgednwie nicht wie ich das berücksichtigen muss.
das skript von meinem prof ist leider alles in allem sehr bescheiden und mehr wie eine flüchtige zusammenfassung geschrieben und weniger als erklärungsgrundlage für einsteiger. Wäre gut wenn mir da jemand helfen könnte.
danke im vorraus.
|
|
02.06.2008 20:38 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Vielleicht hilft es dir, wenn man die gegebene Sprache aufteilt in zwei konkatenierte Sprachen:
L = {a^i b^i | i aus IN} * {c^i | i aus IN}
Wenn du nun eine Grammatik mit Startsymbol S' für die erste Sprache und eine Grammatik mit Startsymbol S'' für die zweite Sprache jeweils einzeln konstruierst, dann lässt sich L durch die Produktionsregel S -> S'S'' erzeugen.
Bei dem Kellerautomaten gehst du so vor:
Konstruiere zuerst einen Kellerautomaten für die erste Sprache: Für jedes gelesene a schreibe Symbol auf den Keller, für jedes gelesene b Lösche Symbol vom Keller. Achte darauf, dass nach einem gelesenen b kein a mehr kommt. Ist der Keller am Ende leer, dann gehe in einen akzeptierenden Zustand, der über eine c-Transition stets zu sich selbst zurückführt. So hast du die zweite Sprache konkateniert.
|
|
|
06.06.2008 12:53 |
|
|
|
