Пампинг лема

Пампинг-лема (Шаблон:Јез-енгл) или лема упумпавања у теоријској информатици описује особину класе формалних језика који нису регуларни односно нису језици са слободним контекстом.

Њено име потиче од енглеске речи -{to pump}-, што значи пумпати. Названа је тако по томе што особине језика доказује процесом који личи на пумпање.

Разликује се више варијанти ове леме, у зависности на које језике се лема примењује: на региучарне или на језике са слободним контекстом.

Дефиниција

Регуларни језици

Нека је ${ℒ}_3$ скуп регуларних језика. За прављење једног регуларног језика мора постојати граматика трећег типа Чомског.

Нека је -{L}- један регуларан језик из ${ℒ}_3$. Онда постоји један природан број -{n}-! из -{N}-, такав да се свака реч -{x}- из -{L}- коју чини -{n}- или више знакова може разложити као -{x = uvw}- уз следећа правила:

1. $\left|v\right|\ge 1$
2. $\left|uv\right|\le n$
3. $\mathrm{\forall }i\ge 0:u{v}^{i}w\in L$

Уколико језик испуњава услове не мора да значи да је регуларан, али сваки који је не испуњава није регуларан.

Језици са слободном синтаксом

Нека је ${ℒ}_2$ класа свих језика који се могу описати граматикама другог типа Чомског тј. свих језика са слободном синтаксом.

Нека је -{L}- један језик са слободном синтаксом, тј. језик из ${ℒ}_2$. Онда постоји константа -{n}- из -{N}- таква да се све речи -{z}- из -{L}- могу раставити као -{z = uvwxy}-, при чему

1. $\left|vx\right|\ge 1$
2. $\left|vwx\right|\le n$
3. $\mathrm{\forall }i\ge 0:u{v}^{i}w{x}^{i}y\in L$