自动机Chomsky范式(CNF)

本文概述

  • 将CFG转换为CNF的步骤
CNF代表Chomsky范式。如果所有生产规则都满足以下条件之一,则CFG(上下文无关文法)为CNF(乔姆斯基范式):
  • 开始生成符号ε。例如,A→ε。
  • 一个非终端生成两个非终端。例如,S→AB。
  • 生成终端的非终端。例如,S→a。
例如:
G1 = {S → AB, S → c, A → a, B → b} G2 = {S → aA, A → a, B → c}

语法G1的生成规则满足为CNF指定的规则,因此语法G1在CNF中。但是,语法G2的生成规则不满足为CNF指定的规则,因为S→aZ包含终止符,然后是非终止符。因此语法G2不在CNF中。
将CFG转换为CNF的步骤步骤1:从RHS中删除开始符号。如果开始符号T在任何生产的右侧,请创建新生产,如下所示:
S1 → S

其中S1是新的开始符号。
步骤2:在语法中,删除空,单位和无用的生产。你可以参考CFG的简化。
步骤3:如果终端与其他非终端或终端一起存在,则从产品的RHS中消除终端。例如,生产S→aA可以分解为:
S → RA R → a

步骤4:使用两个以上的非终端消除RHS。例如,S→ASB可以分解为:
S → RS R → AS

例:
【自动机Chomsky范式(CNF)】将给定的CFG转换为CNF。考虑给定的语法G1:
S → a | aA | B A → aBB | ε B → Aa | b

解:
步骤1:我们将创建一个新产品S1→S,因为起始符号S出现在RHS上。语法将是:
S1 → S S → a | aA | B A → aBB | ε B → Aa | b

步骤2:由于语法G1包含A→ε零产生,因此将其从语法中去除会产生:
S1 → S S → a | aA | B A → aBB B → Aa | b | a

现在,由于语法G1包含单位产出S→B,因此其去除率:
S1 → S S → a | aA | Aa | b A → aBB B → Aa | b | a

还要去除单位产品S1→S,从语法中去除它会产生:
S0 → a | aA | Aa | b S → a | aA | Aa | b A → aBB B → Aa | b | a

步骤3:在生产规则S0→aA | Aa,S→aA | Aa,A→aBB和B→Aa,RHS上的终端a具有非终端。因此我们将终端X替换为:
S0 → a | XA | AX | b S → a | XA | AX | b A → XBB B → AX | b | a X → a

步骤4:在生产规则A→XBB中,RHS有两个以上的符号,将其从语法结果中删除:
S0 → a | XA | AX | b S → a | XA | AX | b A → RB B → AX | b | a X → a R → XB

因此,对于给定的语法,这是必需的CNF。

    推荐阅读