Определение

$\varepsilon$ - свободная ацикличная грамматика (оценка правила) находится в нормальной форме Хомского, если все правила имеют вид: $A \to a$ либо $A \to BC$

Теорема

<aside> 📌 Любая контекстно свободная грамматика эквивалентна грамматике в НФХ

</aside>

Доказательство:

Грамматика: $\varepsilon$ - свободная и ациклична

1. $G = (\Sigma, Г, P, S)$ $\forall a \in \Sigma$ выводит новый нетерминал $A_a \to a$ и заменит вправых частях «а» на «$A_a$»

   Случай 1.

   $A \to B_1, B_2 ... B_n ( n \ge 3)$

   введём новые нетерминалы и добавим правила

   $A \to B_1 D_1$ $D_1 \to B_2D_2$ $....$

   $D_{n-2} \to B_{n-1}B_n$

   Случай 2.

   Пусть есть цепные правила $A_1 \to A_2 \to ... \to A_{k-1} \to A_k$ удалим правила $A_{k-1} \to A_k$ и добавим все правила вида: $A_{k-1} \to \alpha$, где $A_k \to \alpha$ правило исходной грамматики

#Пример

$S \to aAa|B$ $B \to b | A$ $A \to a | bB$

$S \to B \to A \to A_a$ $S \to A_1 AA_1 | B$ $B \to b|A$ $A \to A_1 |A_2|B$ $A_1 \to aA_2 \to b$

$A \to A_2B |a$ $B \to b|A_2B|a$

$S \to A_1AA_1|b|a|A_2B$ $D_1 \to AA_1$

«Алгоритм Кока-Янгера-Касами»

Вход: $w \in \Sigma^+, G \ \text{в НФХ}$

Выход: $w \in L(G)$ или $w \notin L(G)$ т.е. строится вывод $S \rArr^*_G w$

<aside> 💡 Идея: $S \rArr BC \rArr^* w_1w_2$

</aside>

$Г = \{A_1, ..., A_n\}$

$A \in Г$ сопостовляем белеву матрицу $(n$ x $n$$)$

$A[i, j] = \begin{cases} 1 &\text{, \ \ } A \rArr^* w[i, ... i+j-1] \text{подстрока w c i-ой позиции и j-ой длинны}\\ 0 &\text{, \ \ иначе} \end{cases}$

База Индукции (j = 1)

$A[i, 1] = 1$ $\Leftrightarrow$ $A \to w[i] \in P$

Шаг Индукции (k ≥ 2)

$A[i, k] = 1 \Leftrightarrow \exist A \to BC$

$\exist j \exist l (l+j = k)$ $B[i, \ j] = 1$ $C[i+j, \ l] = 1$