Изменения

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

Лемма Огдена

141 байт добавлено, 23:45, 3 января 2017
Нет описания правки
Очевидно, что <tex>B_{p}</tex> КС, если <tex>A_{p}</tex> контекстно-свободен. <tex>B_{p}</tex> является рекурсивно-перечислимым, если и <tex>A_{p}</tex> им является.
Для <tex>B_{p}</tex> будет выполняться лемма Огдена для <tex>n = 4</tex>. Выбрав <tex>A_{p}</tex> таким образом, чтобы он был рекурсивно-перечислимым, мы создадим такой язык. (Такие языки существуют) <ref><A.V. Aho & J.D. Ullman, The Theory of Parsing, Translation and Compilimg, Vol. I, 1972</ref>
== См. также ==
[[Лемма_о_разрастании_для_КС-грамматик|Лемма о разрастании для КС-грамматик]]
 
==Примечания==
 
<references />
== Источники ==
317
правок

Навигация