Пампинг лема за контексно слободни јазици
Од Википедија, слободна енциклопедија
Пампинг лемата за контексно слободни јазици, исто така е позната и како лемата на Бар-Хилел (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 е контексно слободен не е точна.
[уреди] Види исто така
- Пампинг лема за регуларни јазици
- Формални јазици
- Лема на Огден
[уреди] Референци
- 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.
