Question

If we disallow $\epsilon -$ in CFGs, we can simplify the $DK$-test. In the simplified test, we only need to check that each of $DK$’s accept states has a single rule. Prove that a CFG without $\epsilon -$ passes the simplified $DK$-testiff it is a DCFG.

Short answer

The DK-test fails, CFG is a deterministic context-free grammar.

Step-by-step solution

Explain DK-test.

The $DK-$Test is the procedure that determines whether the context-free grammar. For any CFG the DFA is constructed that identify he handles.

Prove that a CFG without ε-rules passes the simplified DK-test iff it is a DCFG. 

Consider in contradiction, that C is not a deterministic CFG. The valid ahb is considered, that has unforced handle h . It has a possibility that some string has another handle. Thus, ahb' can be rewritten as $\overbrace{a}\overbrace{h}\overbrace{b}$ where, b' is a terminal.

While, ah=$\overbrace{a}\overbrace{h}$ , the reduce rule will be changed, because h and $\overbrace{h}$are different handles. Thus, it does not satisfy the DK-test since it has two completed rules.

While ah$\ne$$\overbrace{a}\overbrace{h}$ , assume that the proper prefix of $\overbrace{a}\overbrace{h}$is ah . Assume that s is an accepting state of the input in DK. The s accepts the states because h is the handle.

Hence, the transition must label b' because, $b\text{'}\in \sum _{}\text{'}$ doesnot has null rule. It does not satisfy the DK-test.

Therefore, the DK-test fails, In contradiction to the assumption, CFG is a deterministic context-free grammar.