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

Од Википедија, слободна енциклопедија

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


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

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

u, v, x, y и z, така што |vxy| ≤ p, |vy| ≥ 1, и uv ixy iz е во L за секој интеџер i ≥ 0. 


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

  1. Да претпоставиме дека L е контексно-слободен
    1. Услови:
      1. | vxy | ≤ p. Односно,средината не е предолга.
      2. vy ≠ ε (празно). Бидејќи v и y се делови кои треба да се “пумпаат”, овој услов кажува дека барем еден од стринговите што го пумпаме не смее да биде празен.
      3. За сите i ≥ 0, u vi x yi z се во L. Односно,двата стринга v и y можат да се пумпаат огромен број на пати, вклучувајќи и нула пати, а резултантниот стринг сеуште ќе биде член на L.

2. Ако стрингот w ∈ L каде | w | > p, следи дека w = uvxyz, каде | vxy | ≤ p

3. Сега да избереме вредност за j поголема од p.

4. Кога vxy се појавува во стрингот аj bj cj , vxy не може да содржи повеќе од две различни букви, бидејќи најдесната е j+1 позиција од најлевата c.

  1. Пример: може да биде цел од а букви или цел b од или од c букви , или може да биде составен од a и b или пак од b и c симболи.
    1. Иако стрингот vxy не може да содржи повеќе од две различни букви, а исто така според пампинг лемата не може да биде ни празен, затоа мора да содржи барем една буква.

5. Сега може да почнеме да "пумпаме"

  1. Бидејќи uvxyz е во L, u v2 x y2 z мора исто така да бидат во L. Бидејќи v и y не можат и двете истовремено да бидат празни, | u v2 x y2 z| >

| uvxyz |, затоа додадовме букви.

  1. Но бидејќи vy не ги содржи сите три различни букви, не можеме да додадеме ист број на букви од сите поединечно. Ја напумпавме со повеќе букви и со тоа ја побивме оргиналната дефиниција на L. Затоа ,

u v2 x y2 z не може да биде во L.

6. Дојдовме до контрадикторност. Затоа, нашата првична претпоставка, дека L е контексно-слободна не е точна. KJ