Изменения

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

Существенно неоднозначные языки

267 байт добавлено, 22:47, 15 января 2011
Нет описания правки
Лемма:
<tex>\forall \Gamma \exists k \ge 1: z \in L(\Gamma), |z| \ge k</tex> и в z выбраны хотябы k позиций, то z представимо в виде <tex>z = uvwxy</tex>, где <tex>uvw</tex> или <tex>wxy</tex> содержат хотя бы по одной выбранной позициии <tex>vwx</tex> содержит не более k выбраных позиций и <tex>\exists A</tex> - нетерминал, такой, что <tex>\forall i: S \Rightarrow^* uAy \Rightarrow^* uvAxy \Rightarrow^* uv^i Ax^i y \Rightarrow^* uv^i wx^i y</tex>
Анонимный участник

Навигация