Reguliariųjų išraiškų ir NFA ekvivalentiškumas
Reguliariosios išraiškos, sudarytos iš raidžių, tuščiojo žodžio ir tuščiosios kalbos taikant sąjungą, konkatenaciją ir Kleene žvaigždę, aprašo tiksliai tas kalbas, kurias atpažįsta DFA arba NFA.
Esminės žinios
Reguliariosios išraiškos, sudarytos iš raidžių, tuščiojo žodžio ir tuščiosios kalbos taikant sąjungą, konkatenaciją ir Kleene žvaigždę, aprašo tiksliai tas kalbas, kurias atpažįsta DFA arba NFA. Taikant poaibių konstrukciją, galimų aktyvių NFA būsenų aibės pakeičiamos DFA būsenomis.
Sąlygos ir taikymo ribos
- Kad NFA priimtų žodį, turi egzistuoti bent vienas priimantis skaičiavimas, įskaitant epsilon uždarinį.
- Programavimo reguliariųjų išraiškų plėtiniai, tokie kaip atgalinės nuorodos, nepatenka į šios klasikinės teoremos taikymo sritį.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaita 4: poaibių ir epsilon konstrukcijos bei reguliariųjų išraiškų ekvivalentiškumo teoremos.
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-regular-expressions-nfa
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra