I am trying to build a DPDA for the given grammar:

$S \to aR$
$R \to bRT \ |\ \varepsilon$
$T \to cSR \ |\ \varepsilon$

I tried simplifying grammar first (removing null and unit productions, useless and unreachable symbols), removed axiom $S$ from productions (with correcting spawned null and unit productions, of course). Converting it Greibach normal form I got:

$S \to a\ |\ aR$
$P \to a\ |\ aR$
$R \to b\ |\ bT\ |\ bR\ |\ bRT$
$T \to cP\ |\ cPR$

I am still at loss at how to go about building a DPDA from this. Along the way I've learned DPDA's are usually defined to accept an input string if and only if the whole string has been read and a final state has been reached (regardless of the stack being empty or not).

I am aware that there is no algorithm for converting a NPDA to a DPDA, even when appropriate DPDA for the language exists. I suspect the language defined by my grammar might not be amenable to recognition by a DPDA. Still, if that is the case, I don't know how to prove it.

What am I missing here?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.