177
правок
Изменения
→Алгоритм преобразования грамматики в конечный автомат
{{Лемма
|statement = Не самоприменимая контекстно-свободная грамматика генерирует регулярный язык.
|proof = В качестве конструктивного доказательства приведем рассмотрим алгоритм построения [[Недетерминированные конечные автоматы|конечного автомата]] по грамматике. Также приведем ссылку на формальное доказательство<ref>[http://ac.els-cdn.com/S0019995859800176/1-s2.0-S0019995859800176-main.pdf?_tid=01067c30-c616-11e6-a178-00000aab0f6c&acdnat=1482171029_8a3a81a6f520cf0f9a769aaafbb8babb Noam Chomsky {{---}} A note on phrase structure grammars]</ref>.
}}
