Пампинг лема за контексно слободни јазици

**Пампинг лемата за [[контексно слободен јазик|контексно слободни јазици]]**, исто така е позната и како лемата на Бар-Хилел (Bar-Hillel), е лема која има својства кои важат за сите *контексно слободни јазици*. Нејзината примарна употреба е да докаже декa јазикот не е *контексно слободен*. Пампинг лемата за *контексно слободни јазици* не може да биде користена за докажување дека било кој *не контексно слободен јазик* не е *контексно слободен*. Во некои случаи мора да се користи лемата на Огден (Ogden) која е погенерализирана.

## Формална дефиниција
Ако јазикот L е бесконечен и *контексно слободен*, тогаш постои некоја целобројна вредност p&nbsp;>&nbsp;0 така што секоја низа w во L со |w|&nbsp;≥&nbsp;p (каде p е пампинг должина) може да биде запишано како:

:*w* = *uvxyz* со низи *u*, *v*, *x*, *y* и *z*, така што |*vxy*|&nbsp;≤&nbsp;*p*, |*vy*|&nbsp;≥&nbsp;1, и
:*uv<sup>i</sup>xy<sup>i</sup>z* е во *L* за секој цел број *i* ≥ 0.

## Употреба на лемата
Пампинг лемата  за *контексно слободни јазици* може да се користи за да се покаже дека одредени јазици не се *контексно слободни*. За пример ќе покажеме дека јазикот L&nbsp;=&nbsp;{аj&nbsp;bj&nbsp;cj:&nbsp;j>0} не е *контексно слободен*.

# Да претпоставиме дека  L е *контексно слободен* 
# Услови: 
## | vxy | ≤ p. Односно, средината не е предолга. 
## vy ≠ ε (празно). Бидејќи v и y се делови кои треба да се “пумпаат”, овој услов кажува дека барем еден од стринговите што го пумпаме не смее да биде празен. 
## За сите  i ≥ 0, u vi x yi z се во L. Односно, двете низи v и y можат да се пумпаат огромен број на пати, вклучувајќи и нула пати, а резултантната низа сѐ уште ќе биде член на L. 
#       Ако низата  w ∈ L каде |w|&nbsp;>&nbsp;p, следи дека w&nbsp;=&nbsp;uvxyz, каде |&nbsp;vxy&nbsp;|&nbsp;≤&nbsp;p 
#	Сега да избереме вредност за j поголема од p.
#	Кога vxy се појавува во низата аj&nbsp;bj&nbsp;cj, vxy не може да содржи повеќе од две различни букви, бидејќи најдесната е на j+1 позиција од најлевата c. 
#       Може да биде цел од а букви или цел дел од b од или од c букви, или може да биде составен од a и b или пак од b и c симболи. 
#       Низата vxy не може да содржи повеќе од две различни букви, а исто така според пампинг лемата не може да биде ни празна, затоа мора да содржи барем една буква. 
#	Сега може да почнеме да "пумпаме" 
#       Бидејќи  uvxyz е во L, uv2xy2z мора исто така што бидат во L. Бидејќи v и y не можат и двете истовремено да бидат празни, |uv2xy2z|&nbsp;>&nbsp;|uvxyz|, затоа додадовме букви.
#       Но бидејќи vy не ги содржи сите три различни букви, не можеме да додадеме ист број на букви од сите поединечно. Ја напумпавме со повеќе букви и со тоа ја побивме оригиналната дефиниција на L. Затоа, uv2xy2z  не може да биде во L.
#	Дојдовме до контрадикторност. Затоа, нашата првична претпоставка, дека јазикот L е *контексно слободен* не е точна.

## Поврзано
* Пампинг лема за регуларни јазици
* Формални јазици
* Лема на Огден

## Наводи
*  Section 1.4: Nonregular Languages, pp.&nbsp;77–83. Section 2.3: Non-context-free Languages, pp.&nbsp;115–119.

Категорија:Информатика
Категорија:Програмски јазици
Категорија:Формални јазици
Категорија:Леми