Lema lui Ogden

În teoria limbajului formal, lema lui Ogden oferă o extensie a flexibilității lemei sprawl pentru limbile fără context .

Lema Ogden afirmă că, dacă limbajul L este liber de context, atunci există un număr p > 0 (unde p poate fi sau nu lungimea pompei), astfel încât pentru orice șir w de lungime cel puțin p din L și pentru orice „Markup” p sau mai multe poziții în w , w pot fi reprezentate ca

unde u , v , x , y și z  sunt șiruri astfel încât

1. x conține cel puțin o poziție etichetată,
2. fie u și v conțin poziția marcată, fie și y și z o conțin ,
3. vxy conține cel mult p poziții marcate și
4. uv i xy i z aparține lui L pentru orice i ≥ 0.

Lema lui Ogden poate fi folosită pentru a demonstra că o anumită limbă nu este lipsită de context, în cazurile în care lema de creștere pentru limbile fără context nu este suficientă. Un exemplu ar fi limba { a i b j c k d l  : i = 0 sau j = k = l }. Este util și pentru a demonstra ambiguitatea esențială a unor limbi.

Rețineți că dacă toate pozițiile sunt verificate, această lemă este echivalentă cu lema de pompare pentru limbaje fără context.

Vezi și

• Lema de creștere pentru limbi fără context
• Lema de creștere