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

Од Википедија, слободната енциклопедија
Прејди на: содржини, барај

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

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