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

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

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

w = uvxyz со низи u, v, x, y и z, така што |vxy| ≤ p, |vy| ≥ 1, и
uvixyiz е во L за секој цел број i ≥ 0.

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

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

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

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

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