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

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

Формална дефиниција

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

w = uvxyz со низи u, v, x, y и z, така што |vxy| ≤ p, |vy| ≥ 1, и

uvⁱxyⁱz е во L за секој цел број i ≥ 0.

Употреба на лемата

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

1. Да претпоставиме дека L е контексно слободен
2. Услови:
   1. | vxy | ≤ p. Односно, средината не е предолга.
   2. vy ≠ ε (празно). Бидејќи v и y се делови кои треба да се “пумпаат”, овој услов кажува дека барем еден од стринговите што го пумпаме не смее да биде празен.
   3. За сите i ≥ 0, u vⁱ x yⁱ z се во L. Односно, двете низи v и y можат да се пумпаат огромен број на пати, вклучувајќи и нула пати, а резултантната низа сѐ уште ќе биде член на L.
3. Ако низата w ∈ L каде |w| > p, следи дека w = uvxyz, каде | vxy | ≤ p
4. Сега да избереме вредност за j поголема од p.
5. Кога vxy се појавува во низата а^j b^j c^j, vxy не може да содржи повеќе од две различни букви, бидејќи најдесната е на j+1 позиција од најлевата c.
6. Може да биде цел од а букви или цел дел од b од или од c букви, или може да биде составен од a и b или пак од b и c симболи.
7. Низата vxy не може да содржи повеќе од две различни букви, а исто така според пампинг лемата не може да биде ни празна, затоа мора да содржи барем една буква.
8. Сега може да почнеме да "пумпаме"
9. Бидејќи uvxyz е во L, uv²xy²z мора исто така што бидат во L. Бидејќи v и y не можат и двете истовремено да бидат празни, |uv²xy²z| > |uvxyz|, затоа додадовме букви.
10. Но бидејќи vy не ги содржи сите три различни букви, не можеме да додадеме ист број на букви од сите поединечно. Ја напумпавме со повеќе букви и со тоа ја побивме оригиналната дефиниција на L. Затоа, uv²xy²z не може да биде во L.
11. Дојдовме до контрадикторност. Затоа, нашата првична претпоставка, дека јазикот L е контексно слободен не е точна.

Поврзано

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

Наводи

• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 1.4: Nonregular Languages, pp. 77–83. Section 2.3: Non-context-free Languages, pp. 115–119.