Лемма Огдена

Лемма:

Пусть [math]L[/math] — контекстно-свободный язык над алфавитом [math]\Sigma[/math]. Существует такое [math]n[/math], что для любого слова [math]\omega[/math], длины не менее [math]n[/math], и для любых выделенных в [math]\omega[/math] не менее [math]n[/math] позиций, [math]\omega[/math] может быть представлено в виде [math]\omega=uvxyz[/math], так что: либо [math]uvx[/math], либо [math]xyz[/math] содержат все выделенные позиции; [math]vxy[/math] содержат не более [math]n[/math] выделенных позиций; существует [math]A \in L[/math], такой что [math]S \Rightarrow^{*} uAz \Rightarrow^{*} uvAyz \Rightarrow^{*} uvxyz[/math]

Доказательство:

[math]\triangleright[/math]

comming soon

[math]\triangleleft[/math]