Важность нормальных форм, таких как нормальная форма Хомского, для CFG

Я понимаю, что контекстно-свободные грамматики могут использоваться для представления контекстно-свободных языков. Это может иметь неоднозначность. У нас также есть нормальные формы, такие как нормальная форма Хомского и Грейбаха . Я не мог понять необходимость этого.

Почему они важны в теории языков? Все учебники, о которых я говорил, рассказывают об этих нормальных формах, но ничего не говорят об их важности.

Есть по крайней мере два соответствующих использования.

1. Простота доказательств
   Существует множество доказательств вокруг контекстно-свободных грамматик, включая приводимость и эквивалентность автоматам. Чем проще, тем более ограничен набор грамматик, с которыми вам приходится иметь дело. Поэтому нормальные формы могут быть полезны там.

   В качестве конкретного примера, нормальная форма Грейбаха используется для демонстрации (конструктивно) того, что для каждого КЛЛ существует свободный от транзитных переходов (который не содержит ).$\varepsilon$$\varepsilon$

2. Включает синтаксический анализ
   Хотя КПК можно использовать для анализа слов с любой грамматикой, это часто неудобно. Нормальные формы могут дать нам больше структуры для работы, что упрощает алгоритмы синтаксического анализа.

   В качестве конкретного примера алгоритм CYK использует нормальную форму Хомского. Нормальная форма Грейбаха, с другой стороны, позволяет проводить рекурсивно-спусковой анализ; даже если может потребоваться возврат, сложность пространства линейна.

Нормальная форма Хомского позволяет алгоритму полиномиального времени решать, может ли строка быть сгенерирована грамматикой. Алгоритм довольно ловкий, если вы знаете динамическое программирование ...

Если длина вашего ввода ( ) равна тогда вы берете двумерный массив ( ) dim x .н А н $I$$n$$A$$n$$n$

G I ( i , j $A[i,j]$ обозначает все символы в грамматике которые могут выводить подстроку .$G$$I(i,j)$

Итак, наконец, если содержит начальный символ ( ), то это означает, что строка I может быть получена с помощью что мы и хотели проверить.S $A[1,n]$$S$$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.

Я знаю, что индексы кажутся довольно сумасшедшими. Но в основном вот что происходит.

$\epsilon$