Bekontekstės kalbos: priklausymas ir tuštumas
Baigtinės bekontekstės gramatikos kalbos priklausymo problema yra išsprendžiama: gramatika pertvarkoma į Chomskio normaliąją formą ir netuščiam įvesties žodžiui išvardijami riboto ilgio išvedimai.
Esminės žinios
Baigtinės bekontekstės gramatikos kalbos priklausymo problema yra išsprendžiama: gramatika pertvarkoma į Chomskio normaliąją formą ir netuščiam įvesties žodžiui išvardijami riboto ilgio išvedimai. Tuštumas nustatomas pakartotinai žymint kintamuosius, kurių taisyklėse naudojami tik terminalai arba jau produktyvūs kintamieji; kalba yra netuščia tada ir tik tada, kai pradinis kintamasis pažymėtas.
Sąlygos ir taikymo ribos
- Tuščiojo žodžio epsilon priklausymą nagrinėkite atskirai; tuščioji taisyklė yra produktyvi.
- Priklausymo sprendžiamumas nereiškia, kad savavališkų gramatikų ekvivalentiškumas ar daugiareikšmiškumas yra sprendžiamas.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaitos 7 skaidrės 7–9, apribotas išvedimas Chomsky normaliąja forma (CNF) ir produktyviųjų kintamųjų fiksuotasis taškas; į konversijos įrodymą pateikta nuoroda, o ne nepriklausomai patvirtintas jo teisingumas.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaityti visi 241 glaustai suformuluotas teiginys, prielaidos, atskirai pateiktos lygtys bei sutartiniai žymėjimai ir visos 596 iš šių įrašų išeinančios semantinės sąsajos; peržiūrėta visa autoriaus tikslių šaltinių patikros matrica, apimanti 241 įrašą, ir deklaruoti 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; tai NEREIŠKIA, 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 specialisto patvirtinimas, 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-context-free-decision-methods
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra