内容整理自书本1。
我们从CFG G出发，构建与之相关的DFA DK。其中，CFG（Context Free Grammar）是上下文无关文法，DFA（Deterministic Finite Automate）是确定性的有限自动机。通过检查DK的接受态来判断G是否是确定性的。DK-test要求每一个接受态都要包含以下内容：
恰巧一个完整规则（exactly one completed rule）没有那种终结符紧随点（dot）之后的规则，举个例子： B → u . a v f o r a ∈ ∑ B\to{u.av}\space\space\space\space\space for\space\space a\in{\sum} B→u.av for a∈∑G通过DK-test当且仅当G是DCFG。其中，DCFG是确定性的上下文无关文法。
Introduction to the Theory of Computation ( 3rd edition ) Michael Sipser. p143 ↩︎
