KommuSoft
commented
9 years ago Er bestaat geen algoritme die automatisch (voor alle gevallen) een PDA kan omzetten (of onmiddellijk kan construeren) in een deterministische variant indien dit bestaat.
Bewijs: het is onbeslisbaar of een gegeven non-deterministische PDA een reguliere taal beslist. Stel dat DET_PDA beslisbaar zou zijn, kunnen we eerst DET_PDA laten lopen, indien DET_PDA reject, rejecten we meteen, anders gaan we op zoek naar alle deterministische PDA's (er is een bovengrens op het aantal) en moet er minstens zo'n PDA bestaan die de stacks niet gebruikt (en dus werkt als een DFA). Vermits REGULAR_PDA echter niet beslisbaar is, kan DET_PDA ook niet beslisbaar zijn.
Het verifieren zelf is dus niet op te lossen.
Wel bestaan er heel wat algoritmes die gegeven een grammatica, proberen deterministische parsers te bouwen (bijvoorbeeld LL, LR, LALR, LALR(2) parsers). Een eigenschap is dat wanneer dit niet lukt, er een reduce-reduce conflict in de tabellen komt te staan, in dat geval faalt het algoritme dus. Je kan dus als heuristiek algoritmisch proberen een LL of LALR parser te bouwen, en wanneer dit faalt met enige zekerheid stellen dat het weinig waarschijnlijk is dat er een determinische variant bestaat, maar je kan dus nooit alle gevallen beslissen.
Bijvoorbeeld voor de taal {a^mb^nc^k|m=n} kan je de grammatica:
Goal->M
Goal->M c K
M ->
M ->a M b
K -> c K
K ->Als je deze grammatica invult en het LALR algoritme toepast is er niets aan de hand. Wanneer je echter in plaats van de tweede regel zou vervangen door Goal -> M K zou gebruiken, zullen er twee reduce regels in dezelfde cel, plaatsvinden. Dit wijst dus op ambiguiteit. En inderdaad: de lege string kan je zien als Goal -> M -> epsilon of Goal -> M K -> epsilon K -> epsilon epsilon. Er bestaan algoritmes die dit soort zaken detecteren en automatisch oplossingen voorstellen, maar nogmaals: je kan niet alles algoritmisch eruit filteren zoals dat wel met een reguliere expressie lukt.
warreee
Hoe kan je makkelijk verifiëren of een gegeven CFL deterministisch is of niet? De lange weg is:
Mijn vraag is dus: kan je dit gemakkelijk op zicht doen bvb voor de taal {a^m b^n c^k |m = n}?