grammar - 将 CFG 转换为 Greibach 范式

Question

我们是否需要先将上下文无关语法转换为乔姆斯基范式才能将其转换为格雷巴赫范式？

Answer 1

这个问题可能更适合https://cs.stackexchange.com/，但也有很多人可以在这里回答。

答案是否定的，你不需要通过乔姆斯基范式。教科书中有一种方法：Hopcroft, JE & Ullman JD (1969) Formal Languages and their relationship to Automata , Addison-Wesley, pp.55-57。然而，大多数简单的转换都会首先通过乔姆斯基范式。其他技术更长，并使用 弱格雷巴赫范式作为中间步骤。

如果您想了解该方法的更多详细信息，网上有很多课堂笔记；例如这里，这里；然而，许多课堂笔记只显示通过 CNF 的路线。