Kontekstinės gramatikos ir tiesiškai apriboti automatai
Kontekstinės produkcijos pakeičia αAβ į αγβ, kai γ netuščias; lygiaverčiai, jų netuščių žodžių kalbas galima aprašyti netrumpinančiomis produkcijomis u→v, kur |u|≤|v|, o u turi neterminalą.
Esminės žinios
Kontekstinės produkcijos pakeičia αAβ į αγβ, kai γ netuščias; lygiaverčiai, jų netuščių žodžių kalbas galima aprašyti netrumpinančiomis produkcijomis u→v, kur |u|≤|v|, o u turi neterminalą. Šios kalbos yra būtent tos, kurias atpažįsta nedeterministiniai tiesiškai apriboti automatai, kurių juostos ilgis apribotas pastoviu įvesties ilgio kartotiniu.
Sąlygos ir taikymo ribos
- Čia pagal griežtąjį gramatikos apibrėžimą ε neįtraukiamas. Norint įtraukti ε, leidžiama tik S→ε, kai S nėra jokios produkcijos dešinėje pusėje, o tuščia tiesiškai apriboto automato įvestis nagrinėjama atskirai.
- Įvesties ir juostos abėcėlės yra baigtinės ir fiksuotos; baigtinis juostos takelių skaičius arba didesnė abėcėlė leidžia įtraukti pastovius tiesinius daugiklius. Nedeterminizmas yra būtinas nurodytam lygiavertiškumui, ir neteigiama, kad jį galima pašalinti išlaikant tą patį atminties apribojimą.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Skaidrėse 18 ir 24–25 pateikti apibrėžimai, epsilono išimtis ir lygiavertiškumas su monotoninėmis gramatikomis; skaidrėse 33–38 pateikti tiesiškai apriboti automatai ir Myhill–Landweber–Kuroda teorema su įrodymo schema, paremta atvirkštiniu išvedimu ir mašinos modeliavimu. Išsami gramatikos konstrukcija atvirkštinei implikacijai šiose skaidrėse apibendrinta, bet nėra iki galo įrodyta.
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-sensitive-lba
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra