Пампинг лемата за контексно слободни јазици, исто така е позната и како лемата на Бар-Хилел (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.
Категорија:Информатика Категорија:Програмски јазици Категорија:Формални јазици Категорија:Леми