Kodėl kalba U = 0^n1^n (n>=0) yra netaisyklinga?

/ / paskelbta Kibernetinė sauga, EITC/IS/CCTF skaičiavimo sudėtingumo teorijos pagrindai, „Pushdown Automata“, PDA: „Pushdown Automata“

Klausimas, ar kalba U = \{0^n1^n \vid. n \geq 0\} yra reguliarus, ar ne, yra pagrindinė tema skaičiavimo sudėtingumo teorijos srityje, ypač formalių kalbų ir automatų teorijos studijose. Norint suprasti šią sąvoką, reikia gerai suprasti įprastų kalbų apibrėžimus ir savybes bei jas atpažįstančius skaičiavimo modelius.

Įprastos kalbos ir baigtiniai automatai

Reguliarios kalbos yra kalbų klasė, kurią gali atpažinti baigtiniai automatai, kurie yra abstrakčios mašinos su baigtiniu skaičiumi būsenų. Šias kalbas taip pat galima apibūdinti naudojant reguliariąsias išraiškas ir jas galima sugeneruoti įprastomis gramatikomis. Pagrindinė įprastų kalbų savybė yra ta, kad jas galima atpažinti pagal deterministinius baigtinius automatus (DFA) arba nedeterministinius baigtinius automatus (NFA). DFA sudaro baigtinis būsenų rinkinys, įvesties simbolių rinkinys, perėjimo funkcija, kuri susieja būsenų ir simbolių poras su būsenomis, pradinė būsena ir priėmimo būsenų rinkinys.

Baigtinių automatų galią riboja jų baigtinė atmintis. Jie negali skaičiuoti daugiau nei fiksuotas skaičius, o tai reiškia, kad jie negali sekti savavališko konkretaus simbolio pasikartojimų skaičiaus, nebent skaičius yra apribotas automato būsenų skaičiumi. Šis apribojimas yra svarbus kalbant apie tokias kalbas kaip U = \{0^n1^n \vid. n \geq 0\}.

Nereguliarumas U = \{0^n1^n \vid. n \geq 0\}

Norėdami nustatyti, ar kalba yra taisyklinga, įprastoms kalboms galima naudoti Pumping Lemma. Pumping Lemma suteikia savybę, kurią turi atitikti visos įprastos kalbos, ir ji dažnai naudojama norint parodyti, kad tam tikros kalbos nėra taisyklingos, parodant, kad jos neatitinka šios savybės.

Pumping Lemma teigia, kad bet kuriai įprastai kalbai L, yra siurbimo ilgis p \geq 1 tokia, kad bet kokia eilutė s in L su ilgiu |s| \geq p galima suskirstyti į tris dalis, s = xyz, atitinkantis šias sąlygas:
1. |xy| \leq p,
2. |y| \geq 1ir
3. visiems i \geq 0, eilutė xy^iz yra L.

Norėdami tai parodyti, naudodami Pumping Lemma U = \{0^n1^n \vid. n \geq 0\} nėra taisyklinga, manykite, kad prieštaravimo tai U yra reguliarus. Tada yra siurbimo ilgis p tokia, kad bet kokia eilutė s in U su |s| \geq p galima suskirstyti į dalis x, y, z atitinkančios Pumping Lemmos sąlygas.

Apsvarstykite eilutę s = 0^p1^p in U. Pagal Pumping Lemma, s galima suskirstyti į x, y, z taip, kad |xy| \leq p ir |y| \geq 1. Nuo |xy| \leq p, poeilutė y susideda tik iš 0. Taigi, x = 0^a, y = 0^bir z = 0^{pab}1^p kur 1 \leq b \leq p.

Dabar apsvarstykite eilutę xy^2z = 0^a0^{2b}0^{pab}1^p = 0^{p+b}1^p. 0 skaičius yra p + b, kuris yra didesnis nei p, o lieka 1 s skaičius p. Todėl, xy^2z \notin U nes 0 ir 1 skaičiai nėra lygūs. Šis prieštaravimas rodo, kad prielaida, kad U yra reguliarus yra klaidingas. Vadinasi, U = \{0^n1^n \vid. n \geq 0\} nėra įprasta kalba.

Kalbos be konteksto ir automatas

Kalba U = \{0^n1^n \vid. n \geq 0\} tačiau yra be konteksto kalba (CFL). Nekontekstinės kalbos atpažįstamos išstumiamųjų automatų (PDA), kurie yra galingesni už baigtinius automatus, nes gali naudoti krūvą neribotam informacijos kiekiui saugoti. Ši papildoma atmintis leidžia PDA sekti 0 ir 1 skaičių kalboje U.

PDA skirtas U = \{0^n1^n \vid. n \geq 0\} veikia taip:
1. Jis prasideda pradinėje būsenoje ir skaito 0 iš įvesties, stumdamas kiekvieną 0 į krūvą.
2. Nuskaitęs pirmąjį 1, jis pereina į naują būseną ir pradeda rodyti 0 iš krūvos kiekvienam 1 nuskaitytam iš įvesties.
3. Jei krūva tuščia, kai įvestis yra išnaudota, PDA priima įvestį, nurodydamas, kad 0 skaičius sutapo su 1 s.

Šis dėklo naudojimo mechanizmas, kad būtų suderintas 0 ir 1 skaičius, parodo PDA gebėjimą atpažinti kalbas, kurios nėra įprastos, bet yra be konteksto.

Pavyzdžiai ir kitos pasekmės

Apsvarstykite pavyzdinę eilutę s = 000111 iš kalbos U. PDA apdorotų šią eilutę, įstumdamas kiekvieną 0 į krūvą, kai juos nuskaito. Nuskaičius tris 0, krūvoje būtų trys simboliai, kurių kiekvienas reiškia 0. Kai PDA nuskaito vėlesnius 1, jis ištraukia po vieną simbolį iš krūvos kiekvienam 1. Kai įvestis yra visiškai nuskaityta, krūva tuščia, o tai rodo kad įvestis priimta.

Priešingai, baigtinis automatas negalėtų sekti 0 ir 1 skaičiaus, nes jam trūksta kamino mechanizmo. Be galimybės saugoti ir gauti neribotą skaičių simbolių, baigtinis automatas negali užtikrinti, kad 0 skaičius būtų lygus 1 skaičiui, todėl jis nesugeba atpažinti kalbos. U.

Skirtumas tarp įprastų ir bekontekstinių kalbų yra svarbus teoriniame informatikos moksle ir turi praktinių pasekmių tokiose srityse kaip programavimo kalbos kūrimas ir analizavimas. Apibrėžiant programavimo kalbų sintaksę plačiai naudojamos bekontekstinės gramatikos, generuojančios bekontekstines kalbas. Galimybė efektyviai atpažinti kalbas be konteksto naudojant delninius kompiuterius padeda kurti analizatorius, kurie yra būtini kompiliatoriams ir vertėjams.

Nereguliarumas U = \{0^n1^n \vid. n \geq 0\} pabrėžia baigtinių automatų ribotumą ir pabrėžia, kad reikalingi galingesni skaičiavimo modeliai, tokie kaip išstumiami automatai, kad būtų galima atpažinti platesnę kalbų klasę. Šis skirtumas nėra tik teorinis, bet turi didelę reikšmę praktiniam programavimo kalbų ir jas apdorojančių įrankių kūrimui ir įgyvendinimui.

Kiti naujausi klausimai ir atsakymai apie EITC/IS/CCTF skaičiavimo sudėtingumo teorijos pagrindai:

Peržiūrėkite daugiau klausimų ir atsakymų EITC/IS/CCTF skaičiavimo sudėtingumo teorijos pagrinduose

Daugiau klausimų ir atsakymų:

Tagged pagal: , , , , ,