Лемма Огдена

Материал из Викиконспекты
Перейти к: навигация, поиск
Лемма:
Пусть [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], так что:
  1. либо [math]uvx[/math], либо [math]xyz[/math] содержат все выделенные позиции;
  2. [math]vxy[/math] содержат более [math]n[/math] выделенных позиций;
  3. существует [math]A \in L[/math], такой что [math]S \Rightarrow^{*} uAz \Rightarrow^{*} uvAyz \Rightarrow^{*} uvxyz[/math]