Изменения

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

Лемма Огдена

2 байта убрано, 23:13, 18 января 2017
Пример не КС-языка, для которого выполняется лемма
Не исключено, наконец, что обе накачиваемые цепочки расположены в «зоне» символов <tex>a</tex>. Но тогда одним из указанных выше способов накачки можно уравнять числа либо символов <tex>a</tex> и <tex>b</tex>, либо <tex>a</tex> и <tex>c</tex>.
[[Файл:OgdenaOgden1.png|left|Рис. Цепочки контекстно-свободного языка]]
Заметим, что возможность выделения символов существенно упрощает анализ данного языка, так как позволяет считать, что цепочка <tex>v</tex> может расположиться единственным способом. Иначе, т.е. при использовании леммы о разрастании для кс-языков, решение
задачи было бы, по меньшей мере, сильно затруднено.
 
 
== См. также ==
9
правок

Навигация