50
правок
Изменения
→Алгоритм преобразования грамматики в конечный автомат
{{Лемма
|statement = Не самоприменимая контекстно-свободная грамматика генерирует регулярный язык.
|proof = В качестве конструктивного доказательства, мы приведем алгоритм построения [[Недетерминированные конечные автоматы|конечного автомата]] по грамматике. В источниках есть ссылка на формальное доказательство.
}}
'''foreach''' p '''in''' <tex>P</tex> '''where''' p == <tex> a \rightarrow \beta </tex>
makeFA (<tex> q_0, \beta, q_1 </tex>)
== Апроксимации самоприменимой грамматики ==
В данном разделе покажем методы апроксимации самоприменимой свободной контекстной грамматики <tex> G = \langle N, \Sigma, P, S \rangle</tex> к регулярной грамматике. Для удобства будем считать, что грамматика представлена в [[Нормальная форма Хомского|НФХ]].
