context-free-grammar - 为什么这个 DK 测试是错误的？

Question

我想解决“计算理论导论”Sipser第3版的问题2.24，如下：

令 G 为以下文法：

S → T-

T → TaTb | TbTa | ε

（ - 是结束标记语言的结束符号）

使用 DK 检验证明 G 是 DCFG。描述一个识别 L(G) 的 DPDA

我尝试使用 DK 测试，但这表明 G 不是 DCFG，但这是不可能的，因为我构建了一个识别 L(G) 的 DPDA。

有人能告诉我为什么我运行 DK 测试错误吗？

我不能发布我的工作照片（因为我没有足够的声誉），但我可以解释我做了什么：我构建 DFA DK 以显示 G 是 DCFG，但遵循我在 DFA 中达到的符号 TaTb DK的状态有2个完整的规则

T→TaTb。

T→。

这意味着语法 G 不是 DCFG，但这不是真的。我看不出我做错了什么。

标签： context-free-grammarpushdown-automaton