乔姆斯基范式

Question

为什么我们要将语法转换为乔姆斯基范式？有优势吗？

Answer 1

一方面，您可以在乔姆斯基范式语法上使用 CYK 算法

Answer 2

乔姆斯基范式使多项式时间算法能够决定是否可以通过语法生成字符串。
如果您了解动态编程，那么该算法非常流畅...

如果您的输入 (I) 的长度为 n，那么您将采用一个大小为 nxn 的二维数组 (A)。

A[i,j]表示文法G中所有可以导出子串I(i,j)的符号。

所以最后如果 A[1,n] 包含起始符号（S）那么这意味着字符串 I 可以由 S 导出，这就是我们想要检查的。

def decide (string s,grammar G):
    //base case
    for i=1 to n:
        N[i,i]=I[i]    //as the substring of length one can be generated by only a
                       terminal.
    //end base case

    //induction
    for s=1 to n:       //length of substring
        for i=1 to n-s-1: //start index of substring
            for j=i to i+s-1:   //something else
                 if there exists a rule A->BC such that B belongs to N[i,j] and C
                 belongs to N[j+1,i+s-1] then add A to N[i,i+s-1]
    //endInduction

    if S belongs to N[1,n] then accept else reject.

我知道指数看起来相当疯狂。但基本上这就是发生的事情。

- 我认为基本情况非​​常清楚

- 在归纳步骤中，我们从所有长度小于 s 的解决方案中构建长度 s 子串的解决方案。

- 假设您正在寻找从索引 1 开始的长度为 5 的子字符串 (sub) 的解决方案。然后您启动一个循环（其他部分）......它检查是否存在规则（A ->BC)，使得 B 和 C 导出 sub 的两个连续且不相交的子串，如果是这样，则将所有此类 A 添加到 N[1,6]。

-最后，如果您在 N[1,n] 中有开始符号，那么您接受！

Answer 3

例如，CNF 中的语法（或者更确切地说是它的派生树）用于证明上下文无关语言的泵引理。

Answer 4

使用乔姆斯基范式的优点是：

1. 证明简单
   我们有许多上下文无关语法的证明，包括可还原性和与自动机的等价性。但这些是必须处理的更简单且更受限制的语法集。因此，范式是有帮助的。
   例如，Greibach 范式用于表明每个 CFL（不包含 ε）都存在一个无 ε-跃迁的 PDA。

2.启用解析
PDA用于解析任何语法的单词，这很不方便。范式为我们提供了更多的结构可供使用，从而使解析算法变得更容易。

例如，CYK 算法使用 Chomsky 范式。另一方面，Greibach 范式支持递归下降解析；尽管可能需要回溯，但空间复杂度是线性的。