Нормальная хомская форма

Question

Почему мы переводим грамматику в нормальную форму хомского? Есть ли преимущество?

Answer 1

Например, грамматика в CNF (или, скорее, его деривационное дерево) используется для доказательства накачки леммы для контекстно-свободных языков.

Answer 2

Во-первых, вы можете использовать алгоритм CYK на грамматиках нормальной формы Хомского.

Answer 3

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

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

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.

- скажем, вы нашли решение для подстроки длиной 5 (sub), начиная с индекса 1. Затем вы запускаете цикл (что-то еще):..... который проверяет, существует ли правило (A->BC), такое, что B и C получают две смежные и непересекающиеся подстроки sub и, если это так, добавить все такие А к N [1,6].

-Наконец, если у вас есть начальный символ в N[1,n], тогда вы принимаете!

Answer 4

Преимущества использования нормальной формы Хомского:

1. Простота доказательства. У нас есть много доказательств для контекстно-свободных грамматик, включая приводимость и эквивалентность автоматам. Но это более простой и более ограниченный набор грамматик, с которыми приходится иметь дело. Поэтому нормальные формы полезны. Например, нормальная форма Грейбаха используется, чтобы показать, что для каждой CFL (которая не содержит ε) существует PDA без ε-переходов.

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

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