Ogdenova lema

U teoriji formalnih jezika, Ogdenova lema pruža nešto veću fleksibilnost od svojstva napuhavanja za kontekstno neovisne jezike.

Ogdenova lema kaže da, ako je jezik L kontekstno neovisan, tada postoji neki broj p > 0 (gdje p može ali i ne mora biti duljina napuhavanja) takav da za svaki niz znakova w u L postoji način na koji možemo "označiti" p ili više pozicija u w, tako da w može biti zapisan kao

w = uvxyz

s podnizovima znakova u, v, x, y, i z, takvim da vy ima barem jednu označenu poziciju, vxy ima najviše p označenih pozicija, i

uv ⁱxy ⁱz je u L za svaki i ≥ 0.

Ogdenova se lema može primijeniti za pokazivanje kako određeni jezici nisu kontekstno neovisni, u slučaju da svojstvo napuhavanja za kontekstno neovisne jezike nije dovoljno. Uočimo da je, u slučaju da je svaka pozicija označena, ova lema istovjetna svojstvu napuhavanja za kontekstno neovisne jezike.

Vidjeti također

• svojstvo napuhavanja
• svojstvo napuhavanja za kontekstno neovisne jezike
• svojstvo napuhavanja za regularne jezike

Izvori

• Ogden, W. 1968. A helpful result for proving inherent ambiguity. Mathematical Systems Theory. 2: 191–194

• Hopcroft, Motwani and Ullman. 1979. Automata Theory, Languages, and Computation. Adison Wesley