Изменения

=== Пример ===

<tex>

</tex>

# Изначально множество порождающих нетерминалов состоит из одного элемента <tex>A</tex>.

# Добавим в множество нетерминал <tex>S</tex>, так как существует правило <tex>S\rightarrow Ac</tex>, в правой части которого стоят нетерминал <tex>A</tex>, который есть в множестве, и терминал <tex>c</tex>.

=== Пример ===

<tex>

S\rightarrow AB|CD\\

A\rightarrow EF\\

G\rightarrow AD\\

C\rightarrow c

</tex>

# Возьмём множество, состоящее из единственного элемента: <tex>\lbrace S \rbrace</tex>.

=== Пример ===

<tex>

S\rightarrow AS|BS|s \\

E\rightarrow EF|FF \\

A\rightarrow a \\

F\rightarrow f

<tex>

S\rightarrow AS|s \\

E\rightarrow EF|FF \\

A\rightarrow a \\

F\rightarrow f

<tex>

S\rightarrow AS|s \\

A\rightarrow a

=== Замечание ===

Шаги алгоритма нельзя менять местами.

<tex>

S\rightarrow AB|a \\

A\rightarrow b

</tex>

Все нетерминалы в этой грамматике достижимы. Однако, если удалить <tex>B</tex> как непорождающий, то нетерминал <tex>A</tex> станет недостижимым.

== См. также ==

* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]

* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]

== Литература ==

* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)

[[Категория: Теория формальных языков]]

[[Категория: Контекстно-свободные грамматики]]