我刚刚了解到,Regular Grammars有相应的Finite State Acceptors,这将对应于Regular Expressions。是否有与Context Free Grammars等效的转换?据我所知,上下文无关语法可以用Push Down Automata来表示,而这又对应于什么呢?
感谢那些能让我摆脱这一切的人。
Shen的书“算法和编程。问题和解决方案”。问题本身是由M. Sipser传达的。作者要求读者定义一个上下文无关文法,该文法生成以下语言: {X2Y | X ∈ {0, 1}*, Y ∈ {0, 1}*, X ≠ Y}。首先,我不能理解这样的语言怎么可能是上下文无关的(从我的新手的角度来看):X和Y可以是任何序列,但它们不能同时是一个序列。对我来说,这似乎是一个上下文相关的属性。“