Пампинг лема

Из пројекта Википедија

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

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

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

[уреди] Дефиниција

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

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

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

$\left| v \right| \ge 1$
$\left| uv \right| \le n$
$\forall i \ge 0 : uv^iw \in L$

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

[уреди] Језици са слободном синтаксом

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

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