Chr*_*gro 11 theory grammar context-free-grammar chomsky-normal-form
我试图证明以下内容:
如果G是乔姆斯基范式中的无上下文语法,那么对于任何字符串w属于长度n≥1的L(G),它需要恰好2n-1步才能得出w的任何推导.
我该如何证明这一点？
tem*_*def 13
作为暗示 - 因为Chomsky Normal Form的每个作品都有这种形式
S→AB,非终端A和B,或形式
S→x,对于终端x,
然后派生一个字符串将以下列方式工作:
应用第一种形式的产生将增加从k到k + 1的非终结符的数量,因为你用一个非终结符号(+2)替换一个非终结符号(-1)以获得+1非终结符号的净增益.由于您从一个非终结符号开始,这意味着您需要执行第一个表单的n - 1个作品.然后你需要n个更多的第二种形式来将非终结符转换为终端,总共给出n +(n - 1)= 2n - 1个作品.
要说明的是,你需要确切地这么多,我会建议由矛盾做了证明,并表明你不能与任何更多或更少的任何做到这一点.作为提示,尝试计算每种类型的制作数量,并显示如果它不是2n - 1,则字符串太短,或者您仍然会留下非终结符号.
希望这可以帮助!