Нормальная форма Хомского позволяет алгоритму полиномиального времени решать, может ли строка быть сгенерирована грамматикой.
Алгоритм довольно ловкий, если вы знаете динамическое программирование ...
Если длина вашего ввода (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 и, если это так, добавляют все такие A к N [1,6].
-Наконец, если у вас есть начальный символ в N [1, n], вы принимаете!