# When our two-state PDA constructed from CFG is non-deterministic PDA?

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


• 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. – Hendrik Jan Jun 3 '20 at 11:09
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.