Паминг лема за контексно-слободни граматики
Од Википедија, слободна енциклопедија
Исто така е позната и како лемата на Бар-Хилел (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} не е контексно-слободен.
- Да претпоставиме дека L е контексно-слободен
- Услови:
- | vxy | ≤ p. Односно,средината не е предолга.
- vy ≠ ε (празно). Бидејќи v и y се делови кои треба да се “пумпаат”, овој услов кажува дека барем еден од стринговите што го пумпаме не смее да биде празен.
- За сите 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.
- Пример: може да биде цел од а букви или цел b од или од c букви , или може да биде составен од a и b или пак од b и c симболи.
- Иако стрингот vxy не може да содржи повеќе од две различни букви, а исто така според пампинг лемата не може да биде ни празен, затоа мора да содржи барем една буква.
5. Сега може да почнеме да "пумпаме"
- Бидејќи uvxyz е во L, u v2 x y2 z мора исто така да бидат во L. Бидејќи v и y не можат и двете истовремено да бидат празни, | u v2 x y2 z| >
| uvxyz |, затоа додадовме букви.
- Но бидејќи vy не ги содржи сите три различни букви, не можеме да додадеме ист број на букви од сите поединечно. Ја напумпавме со повеќе букви и со тоа ја побивме оргиналната дефиниција на L. Затоа ,
u v2 x y2 z не може да биде во L.
6. Дојдовме до контрадикторност. Затоа, нашата првична претпоставка, дека L е контексно-слободна не е точна. KJ