Reguliariųjų kalbų išpūtimo lema
Jei kalba yra reguliarioji, egzistuoja toks p≥1, kad kiekvieną priimamą žodį x, kurio |x|≥p, galima išskaidyti į uvw taip, kad |uv|≤p, |v|≥1 ir uvᵐw būtų priimamas visiems m≥0.
Esminės žinios
Jei kalba yra reguliarioji, egzistuoja toks p≥1, kad kiekvieną priimamą žodį x, kurio |x|≥p, galima išskaidyti į uvw taip, kad |uv|≤p, |v|≥1 ir uvᵐw būtų priimamas visiems m≥0. Norint įrodyti, kad kalba nėra reguliarioji, reikia parodyti, kad kiekvienam leidžiamam pasirinkto žodžio išskaidymui išpūtimo sąlyga netenkinama.
Sąlygos ir taikymo ribos
- Išskaidymas gali priklausyti nuo x; išpūtimo laipsnio rodiklis yra laisvai pasirenkamas.
- Tai būtina reguliarumo sąlyga, bet ne pakankamas kriterijus.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaitos 5 skaidrės 18–21, įrodymas remiantis pasikartojančia būsena ir apriboto ilgio priešdėlio sąlyga.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaitytas visas 241 glaustas teiginys, hipotezės, atskirai pateiktos lygtys bei susitarimai ir visos 596 kilmės semantinės sąsajos; peržiūrėta visa autoriaus 241 įrašo tikslių šaltinių patikros matrica ir nurodyti apribojimai. Siekiant aprėpti visą įrašų rinkinį, perskaityti 105 ankstesni faktiškai paveldėti matematikos ir informacijos įrašai. Toliau išvardyti tiksliniai nepriklausomai peržiūrėti pirminių šaltinių skyriai; tuo NETEIGIAMA, kad kiekvienas cituojamas šaltinis ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atliekama informacinio turinio peržiūra, o ne žmogaus atliekamas dalykinis sertifikavimas, išsamus vadovėlio atkūrimas ar eksperimentinis atkartojimas. Patvirtinimo įrašas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-regular-pumping-lemma
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra