Vienodo ilgio blokų kalbos, kuri nėra bekontekstė, pavyzdys
Kalba {0ⁿ1ⁿ2ⁿ:n≥0} nėra bekontekstė.
Esminės žinios
Kalba {0ⁿ1ⁿ2ⁿ:n≥0} nėra bekontekstė. Pasirinkus tariamą pumpavimo ilgį p, imamas žodis 0ᵖ1ᵖ2ᵖ; atkarpoje vxy, kurios ilgis ne didesnis už p, negali būti ir 0, ir 2. Pumpuojant žemyn pašalinamas bent vienas simbolis iš ne daugiau kaip dviejų blokų, o trečiojo bloko simbolių skaičius lieka p, todėl lygybė pažeidžiama.
Sąlygos ir taikymo ribos
- Argumentas apima kiekvieną išskaidymą, leidžiamą pagal bekontekščių kalbų pumpavimo lemą.
- Šis pavyzdys parodo automato su dėklu (PDA) ir bekontekstės gramatikos (CFG) ribotumą; Tiuringo mašina arba kontekstinis modelis vis tiek gali nuspręsti, ar žodis priklauso šiai kalbai.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaitos 5 skaidrė 6: tris vienodo ilgio blokus nagrinėjantis įrodymas, apimantis visus išskaidymus, su aiškiai išdėstytu simbolių skaičiavimo argumentu pumpuojant žemyn, kai i=0.
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-non-context-free-equal-three-blocks
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra