_Rhodan_
Grünschnabel
Dabei seit: 03.02.2013
Beiträge: 4
 |
|
| ist das eine kontextfreie Grammatik? |
     |
Hi, ich hoffe, mir kann jemand aus einer Zwickmühle helfen. Ich habe folgende Grammatik (abgekürzt):
T = {a,b}
P = {(S -> aSa | bSb | aa | bb | a | b)}
Nun soll ich nachweisen, dass die von dieser Grammatik erzeugte Sprache nicht mit einem Kellerautomaten erkannt werden kann. Nun ja, gemeint ist wohl ein deterministischer KA. Intuitiv ist mir das klar, da wenn ich nur von links nach rechts lesen kann, nicht erkenne, wann ich die Hälfte überschreite.
Nur ... wenn es keinen Kellerautomaten hierzu gibt, dürfte es keine kontextfreie Grammatik (Sprache) sein. Nach den Regeln, die ich kenne ist es aber eine kontextfreie Grammatik.
Was stimmt nun?
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von _Rhodan_: 03.02.2013 18:56.
|
|
