Bekonteksčių kalbų pumpavimo lema
Kiekvienai bekontekstei kalbai L egzistuoja toks p≥1, kad kiekvieną w∈L, kuriam |w|≥p, galima išskaidyti kaip w=uvxyz taip, kad |vxy|≤p, |vy|≥1 ir uvⁱxyⁱz∈L kiekvienam sveikajam skaičiui i≥0.
Esminės žinios
Kiekvienai bekontekstei kalbai L egzistuoja toks p≥1, kad kiekvieną w∈L, kurio |w|≥p, galima išskaidyti kaip w=uvxyz taip, kad |vxy|≤p, |vy|≥1 ir uvⁱxyⁱz∈L kiekvienam sveikajam skaičiui i≥0. Pakankamai ilgame sintaksinės analizės medžio kelyje pasikartojantis kintamasis leidžia kartu pumpuoti dvi jį supančias dalis.
Sąlygos ir taikymo ribos
- Teigiama, kad egzistuoja tinkamas išskaidymas, ir jis gali priklausyti nuo w; norint paneigti, kad kalba yra bekontekstė, reikia parodyti, jog kiekvienam leistinam išskaidymui egzistuoja toks i, kuriam sąlyga netenkinama.
- Ši būtina sąlyga pati savaime neapibūdina visų bekonteksčių kalbų.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaitos 5 skaidrės 3–5: lema su kvantoriais, sintaksinės analizės medžio konstrukcija su pasikartojančiu kintamuoju, netuščios pumpuojamos dalys ir apriboto ilgio atkarpa.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaityti visi glaustai suformuluoti teiginiai (241), hipotezės, pateiktos lygtys ir susitarimai bei visos kilmės semantinės sąsajos (596); peržiūrėta visa autoriaus sudaryta 241 įrašo tikslių šaltinių patikros matrica ir deklaruoti apribojimai. Siekiant aprėpti visą įrašų rinkinį, perskaityti 105 ankstesni faktiškai paveldėti matematikos ir informacijos įrašai. Toliau išvardyti tikslingai ir nepriklausomai peržiūrėti pirminių šaltinių skyriai; tuo NETEIGIAMA, kad kiekvieno cituojamo šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atlikta informacinio turinio peržiūra, o ne žmogaus eksperto patvirtinimas atitinkamoje mokslo srityje, išsamus vadovėlio atkūrimas ar eksperimentinis pakartojimas. Peržiūros įrašas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-context-free-pumping-lemma
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra