Вход
Контекстно-свободная грамматика
Выход
Эквивалентная входной грамматике грамматика в НФХ
Алгоритм
- По входной грамматике построить приведенную грамматику, используя алгоритм из теоремы
- По построенной в предыдущем пункте грамматике, построить эпсилон-свободную грамматику, используя алгоритм из теоремы
- По построенной в предыдущем пункте грамматике, построить приведенную грамматику, используя алгоритм из теоремы
- По построенной в предыдущем пункте грамматике, построить ациклическую грамматику, опираясь на следствие. на очередной итерации используя алгоритм из теоремы
Должна получиться эквивалентная исходной приведенная, эпсилон-свободная, ацикличная грамматика
- По построенной в предыдущем пункте грамматике, построить грамматику, с правилами, удовлетворяющими условию леммы
- По построенной в предыдущем пункте грамматике, построить грамматику, с правилами вывода, удовлетворяющими условию леммы (лучше для понимания, на мой взгляд алгоритм с сайта itmo)
- По построенной в предыдущем пункте грамматике, построить грамматику, с правилами вывода, удовлетворяющими условию леммы
**Должна получиться эквивалентная исходной грамматика в НФХ в силу теоремы