将CFG转换为Greibach范式

Question

我们是否需要先将上下文无关语法转换为Chomsky范式，然后将其转换为Greibach范式？

Answer 1

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

答案是no，您不需要经过Chomsky范式。教科书中有一种方法: Hopcroft，J.E & Ullman J.D. (1969)正式语言及其与自动机的关系，Addison，第55-57页。然而，大多数简单的转换首先要经过Chomsky范式。其他技术更长，使用弱Greibach范式作为中间步骤。

如果您想了解更多关于该方法的详细信息，网络上有大量的类注释；例如，这里，这里；然而，许多类注释只显示通过CNF的路由。