Изменения

Перейти к: навигация, поиск

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

346 байт добавлено, 20:39, 11 октября 2010
Нет описания правки
*<tex>S \rightarrow \varepsilon</tex> (при условии, что <tex>S</tex> не содержится в правых частях правил)
Избавимся от правил, в правых частях которых записаны два символа, один из которых является терминалом, то есть правил вида <tex>A \rightarrow Bc</tex> и <tex>A \rightarrow bc</tex>.
Введем для каждого терминала <tex>a</tex> "персональный" нетерминал <tex>N_a</tex>. Затем правила вида <tex>A \rightarrow Bc</tex> заменим парой правил <tex>A \rightarrow BN_с</tex> и <tex>N_c \rightarrow c</tex>, а правила вида <tex>A \rightarrow bc</tex> - тройкой правил <tex>A \rightarrow N_bN_c</tex>, <tex>N_b \rightarrow b</tex> и <tex>N_c \rightarrow c</tex>.
142
правки

Навигация