解析平衡括号 CNF

Question

我有语法S -> (S)S | empty

我把它转换成了这样的乔姆斯基范式

S -> AS | empty
A -> LB
B -> SR
L -> (
R -> )

我不确定我是否正确转换了它，但是我如何使用 CNF

解析这个输入 ()()

Answer 1

逆向推导如下：


  <b>S</b>        S → AS   
→ <b>A</b>S       A → LB
→ <b>L</b>BS      L → (
→ (<b>B</b>S      B → SR
→ (<b>S</b>RS     S → ε
→ (<b>R</b>S      R → )
→ ()<b>S</b>      S → AS   
→ ()<b>A</b>S     A → LB
→ ()<b>L</b>BS    L → (
→ ()(<b>B</b>S    B → SR
→ ()(<b>S</b>RS   S → ε
→ ()(<b>R</b>S    R → )
→ ()()<b>S</b>    S → ε
→ ()()

解析平衡括号 CNF

Parse balanced parentheses CNF

grammar

chomsky-normal-form