We can always convert our GNF-CFG/CNF-CFG to a two-state PDA but i'm wondering when our PDA is non-deterministic? i'm sure we can not make DPDA for non-Deterministic-CFL , and i suspect that same rule which applied for differing between DCFG and non-Deterministic-CFG also applied here. i mean when we have non-Deterministic δ (delta) implied non-Deterministic edge in our PDA. if my suspicion is right , then for every DCFL exist at least one DPDA with two state. Am i right?

R ≝ Production Rules of CFG
(x,y,"LBL") is a labeled-edge between x and y with “LBL” as a label 
∀r∊R: r= (A,aⱰ) ( A∊V ⋀ a∊T ∧ Ɒ∊V*) add (q,q,"a,A/Ɒ") to E
Add (q,q,"ε,z/Sz′") to E
Add (q,f,"ε,z′/z′") to E

enter image description here

  • 2
    $\begingroup$ What is your definition of DCFG? Note that wikipedia defines the deterministic CFL as languages defined by deterministic PDA. It leaves open what are deterministic grammars. $\endgroup$ Jun 3, 2020 at 11:09
  • $\begingroup$ @HendrikJan i asked 3 more question in comment bellow your answer, please answer it 💐 $\endgroup$ Jun 3, 2020 at 15:49

1 Answer 1


Your construction starts with a CFG $G$ in Greibach normal form. So each of the productions of $G$ is of the form $A \to a \alpha$, with $A$ nonterminal, $a$ terminal and $\alpha$ a string of nonterminals. Such a production is then directly translated into a PDA instruction $(q,a,A) \mapsto (q,\alpha)$. "read $a$ from the tape, pop $A$ and push $\alpha$"

In general PDA is deterministic if there is no configuration in which two different instructions can be applied. So, no two instructions in the same state, the same input symbol, and the same top of stack. Looking back at the CFG that means there are no two productions of the form $A \to a \alpha$, $A \to a \alpha' $, with $\alpha\neq \alpha' $. If there are two such productions, then in configuration $(q,aw,A\gamma)$ - state $q$, string $aw$ to be read, and $A\gamma$ on the stack, the PDA can make to moves, pushing $\alpha$ or $\alpha'$.

This analysis is not complete. There are two additional instructions $(q,\varepsilon,Z) \mapsto (q,SZ')$ ("on initial stack symbol $Z$ push the axiom of the grammar") and $(q,\varepsilon,Z') \mapsto (f,Z')$ ("when the stack is empty, derivation has ended, move to final state"). Although these are $\varepsilon$ instructions, they can only be applied when none of the CFG rules is applicable (start and end) so they will not cause nondeterminism.

  • $\begingroup$ I have 3 more question: 1- In Greibach form we can have rules like (𝐴,𝑎𝛼) with (𝐴,𝑎𝛼′) is this rules always cause nondeterminism like what happened in equivalent PDA with description above? 2- In s-grammar [P. Linz, 4th ed. , p. 139] there is no rules such that (𝐴,𝑎𝛼) with (𝐴,𝑎𝛼′) so there is no nondeterminism in equivalent PDA with description above in conclusion every languages described by s-grammar is deterministic but is there at least one s-grammar for every possible DCFL? 3- in conclusion for every DCFL exist at least one DPDA with two state, is it right? $\endgroup$ Jun 3, 2020 at 15:57
  • 1
    $\begingroup$ (1) When you have two of such rules the PDA obtained will be nondeterministic: it can continue in two different ways. (2) Simple grammars don't have this and lead to deterministic PDA with one state, but (3) I do not think that every deterministic PDA can be reduced to two states. For nondeterministic PDA yes, but I have never seen it for DPDA. This then also means that we do not always have a simple grammar for a DCFL. And Linz states: "Unfortunately, not all features of a typical programming language can be expressed by an s-grammar." $\endgroup$ Jun 3, 2020 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.