Analiza leksikore. Gjuhë të rregullta dhe makina me gjendje të fundme
nga numri i përgjithshëm i karaktereve të alfabetit të simboleve dhe shenjave dhe kllapave të funksionimit në hyrjen r.Baza. Automat për shprehjet me gjatësi 1: dhe janë paraqitur në figurën e mëposhtme.
Oriz. 5.1.
Vini re se për secilën nga këto tre automata, grupi i gjendjeve përfundimtare përbëhet nga një gjendje e vetme.
Hapi i induksionit. Tani supozojmë se për çdo shprehje të rregullt të gjatësisë = 1, fjala w mund të ndahet në k nënfjalë: w=w 1 w 2 ... w k dhe kaq. Për çdo i= 1,... ,k fjala w i përkthehet q 0 1 në q f 1 . Pastaj për fjalën w në diagramin M ka një shteg
Prandaj, . Anasjelltas, nëse ndonjë fjalë e përkthen q 0 në q f , atëherë ose ekziston ose bartet nga një shteg që, pasi ka kaluar nga q 0 në q 0 1 dhe më pas ka kaluar disa herë përgjatë shtegut nga q 0 1 në q f 1 dhe duke u kthyer nga q f 1 në q 0 1 me -tranzicion, në fund nga q f 1 nga -tranzicioni përfundon në q f . Prandaj një fjalë e tillë.
Nga teorema 4.2 dhe 5.1 ne marrim drejtpërdrejt
Përfundimi 5.1. Për çdo shprehje të rregullt, mund të ndërtohet në mënyrë efektive një makinë përcaktuese e gjendjes së fundme që njeh gjuhën e përfaqësuar nga ajo shprehje.
Ky pohim është një nga shembujt e teoremave të sintezës: bazuar në përshkrimin e një detyre (gjuha si shprehje e rregullt), një program (DFA) që e kryen është ndërtuar në mënyrë efektive. E kundërta është gjithashtu e vërtetë - një teoremë e analizës.
Teorema 5.2. Për çdo makinë përcaktuese (ose jopërcaktuese) me gjendje të fundme, është e mundur të ndërtohet një shprehje e rregullt që përfaqëson gjuhën e njohur nga ajo makinë.
Vërtetimi i kësaj teoreme është mjaft teknik dhe përtej qëllimit të kursit tonë.
Kështu, mund të konkludojmë se klasa e gjuhëve të fundme automatike përkon me klasën e gjuhëve të rregullta. Tani e tutje do ta quajmë thjesht klasën e gjuhëve automatike.
Automati M r, i cili është ndërtuar në vërtetimin e Teoremës 5.1
Përkufizimet themelore Shprehjet e rregullta në alfabetin Σ dhe bashkësitë e rregullta që ato shënojnë përcaktohen në mënyrë rekursive si më poshtë: 1) – shprehje e rregullt që tregon një bashkësi të rregullt; 2) e – shprehje e rregullt që tregon një bashkësi të rregullt (e); 3) nëse një Σ, atëherë a është një shprehje e rregullt që tregon një grup të rregullt (a); 4) nëse p dhe q janë shprehje të rregullta që tregojnë bashkësi të rregullta P dhe Q, atëherë a) (p+q) është një shprehje e rregullt që tregon P Q; b) pq – shprehje e rregullt që tregon PQ; c) p* – shprehje e rregullt që tregon P*; 5) asgjë tjetër nuk është një shprehje e rregullt.
Përkufizimet bazë Prioriteti: * (përsëritje) – prioriteti më i lartë; lidhja; + (bashkim). Pra 0 + 10* = (0 + (1 (0*))). Shembuj: 1. 01 do të thotë (01); 2. 0* – (0*); 3. (0+1)* – (0, 1)*; 4. (0+1)* 011 – nënkupton grupin e të gjithë zinxhirëve të përbërë nga 0 dhe 1 dhe që mbarojnë me zinxhirin 011; 5. (a+b) (a+b+0+1)* nënkupton bashkësinë e të gjithë zinxhirëve (0, 1, a, b)* duke filluar me a ose b.
Përkufizimet bazë të Lemës: 1) α + β = β + α 2) * = e 3) α + (β + γ) = (α + β) + γ 4) α(βγ) = (αβ)γ 5) α( β + γ) = αβ + αγ 6) (α + β)γ = αγ + βγ 7) αe = eα = α 8) α = 9) α+α* = α* 10) (α*)* = α* 11) α+α = α 12) α+ = α
Marrëdhënia midis RT dhe RM RM janë gjuhë të krijuara nga RT. Për shembull: x = a+b, y = c+d, x X = (a, b), y Y = (c, d), x + y X Y = (a, b, c, d). Lidhja: xy XY = (ac, ad, bc, bd). k(u+o)t (k)(u, o)(t) = (balenë, mace) ose nga Lemat nr. 5 dhe nr. 6 k(u+o)t = balenë + mace (balenë, mace) . Përsëritja: x = a, x* X* = (e, a, aaa, …), d.m.th. x* = e + xxx + …
Lidhja ndërmjet RP dhe RM Përsëritja e bashkimit dhe bashkimit: (xy)* = e + xyxyxy + … (x + y)* = e + (x + y)(x + y) + … = = e + xx + xy + yx + yy + xxx + … Shembull: 0 + 1(0+1)* (0) ((1) (0, 1)*) = (0, 1, 10, 11, 100, 101, 110, 111… ). Bashkimi është komutativ: x + y = y + x Lidhja nuk është: xy ≠ yx
Komunikimi ndërmjet RM dhe RM Shembuj për prioritet: x + yz (x, yz), (x + y)z (xz, yz), x + y* (e, x, y, yyy, yyyy, ...), (x + y)* (e, x, y, xx, xy, yx, yy, xxx, …), (xy)* (e, xyxy, …), xy* (x, xyy, xyyy, …). Lemat e reja: a* + e = a*; (a + e)* = a*; a*a* = a*; e* = e; etj.
Sisteme të rregullta ekuacionesh Ekuacion me koeficientë të rregullt X = a. X + b ka një zgjidhje (pika fikse më e vogël) a*b: aa*b + b = (aa* + e)b = a*b Sistemi i ekuacioneve me koeficientë të rregullt: X 1 = α 10 + α 11 X 1 + α 12 X 2 + … + α 1 n. Xn X 2 = α 20 + α 21 X 1 + α 22 X 2 + … + α 2 n. Xn……………………………. . Xn = αn 0 + αn 1 X 1 + αn 2 X 2 + … + αnn. Xn Të panjohura – Δ = (X 1, X 2, …, Xn).
Sisteme të rregullta ekuacionesh Algoritmi i zgjidhjes (metoda e Gausit): Hapi 1. Vendosni i = 1. Hapi 2. Nëse i = n, shkoni në hapin 4. Përndryshe, shkruani ekuacionet për Xi në formën Xi = αXi + β (β = β 0 + βi +1 Xi+1 + … + βn. Xn). Pastaj, në krahun e djathtë për ekuacionet Xi+1, ..., Xn, zëvendësojmë Xi me shprehjen e rregullt α*β. Hapi 3. Rriteni i me 1 dhe kthehuni në hapin 2. Hapi 4. Shkruani ekuacionin për Xn si Xn = αXn + β. Shkoni në hapin 5 (me i = n). Hapi 5. Ekuacioni për Xi është Xi = αXi + β. Shkruani në dalje Xi = α*β, në ekuacionet për Xi– 1, …, X 1, duke zëvendësuar α*β në vend të Xi. Hapi 6. Nëse i = 1, ndaloni, përndryshe uleni i me 1 dhe kthehuni në hapin 5.
Transformimi i DFA në RT Për DFA M = (Q, Σ, δ, q 0, F) përpilojmë një sistem me koeficientë të rregullt ku Δ = Q: 1. vendos αij: = ; 2. nëse δ(Xi, a) = Xj, a Σ, atëherë αij: = αij + a; 3. nëse Xi F ose δ(Xi,) = HALT, atëherë αi 0: = e. Pas zgjidhjes, PV e dëshiruar do të jetë X 1 = q 0.
Konvertimi i DFA në RV Shembull: për një numër me pikë fikse marrim sistemin q 0 = + q 0 + sq 1 + pq 2 + dq 3 + q 4 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 Këtu: s – shenja e numrit, s = “+” + “–”; p – presje dhjetore, p = "."; d – numrat, d = “0” + “1” + … + “9”.
Konvertimi i DFA në RT Zgjidhja: q 0 = *(sq 1 + pq 2 + dq 3 + q 4 +) = sq 1 + pq 2 + dq 3 q 1 = + q 0 + q 1 + pq 2 + dq 3 + q 4 = pq 2 + dq 3, q 2 = + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4, q 3 = e + q 0 + q 1 + q 2 + dq 3 + pq 4 = dq 3 + pq 4 + e, q 4 = e + q 0 + q 1 + q 2 + q 3 + dq 4 = dq 4 + e. Nga ekuacioni i tretë: q 3 = dq 3 + pq 4 + e = d*(pq 4 + e). Nga ekuacioni i katërt: q 4 = dq 4 + e = d*.
Shndërrimi i DFA në RT Goditja e kundërt: q 3 = d*(pq 4 + e) = d*(pd* + e), q 2 = dq 4 = dd*, q 1 = pq 2 + dq 3 = pdd * + dd *(pd* + e), q 0 = sq 1 + pq 2 + dq 3 = s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Kështu, kjo DFA korrespondon me RT s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e). Le ta thjeshtojmë: s(pdd* + dd*(pd* + e)) + pdd* + dd*(pd* + e) = = spdd* + sdd*(pd* + e) + pdd* + dd*(pd* + e) = (s + e)(pdd* + dd*(pd* + e)) Për një shënim më të shkurtër, mund të përdorni përsëritjen pozitive aa* = a*a = a+: (s + e)(pdd* + dd* (pd* + e)) = (s + e)(pd+ + d+pd* + d+)
Konvertimi i DFA në RT Hartimi i grafikut të funksionit të tranzicionit DFA në operacionet bazë me shprehje të rregullta: q 0 a b a q 1 q 2 q 1 q 0 a+b a b ab q 2 a*
Konvertimi i DFA në RT Kombinime më komplekse të operacioneve: q 0 a q 1 b b b q 0 a q 2 q 1 (a + e)b c b q 0 q 2 ab(cab)* q 0 (a + b)* q 0 a q 1 aa* = a+ q 0 a q 1 a b a a a (ab)+ q 2 b q 1 c e + (a + b)c*
Konvertimi i DFA në RT Për RT (s + e)(pd+ + d+(pd* + e)): q 0 p q 2 d s p q 1 d d q 3 d p q 4 d q 5 d
Programimi RV Shprehje të rregullta: E integruar në shumë gjuhë programimi (PHP, Java. Script, ...); Zbatuar si komponentë plug-in (për shembull, klasa Regex për platformën .NET). Dallimet në format e shënimeve: x? = x + e x(1, 3) = x + xxx, etj.
Programimi i konstrukteve RT të klasës Regex (Sistemi. Tekst. i rregullt. Shprehje): Interpretimi i simboleve të sekuencës Escape b Kur përdoret në kllapa katrore, korrespondon me simbolin "←" (u 0008) t, r, n, a, f, v Tab (u 0009), kthim me karrocë (u 000 D), linjë e re (u 000 A), etj. c. X Karakteri kontrollues (p.sh. c. C është Ctrl+C, u 0003) e Escape (u 001 B) ooo karakteri ASCII në oktal xhh Karakteri ASCII në heksadecimal uhhhh karakter Unicode Karakteri i mëposhtëm nuk është një karakter i veçantë RT. Ky simbol duhet të përdoret për t'i shpëtuar të gjithë karaktereve speciale. Shembull (shembulli tregon një model dhe një varg kërkimi, përputhjet e gjetura janë të nënvizuara në varg): @"rnw+" – "rn. Këtu ka dy rreshta."
Programimi RV Nëngrupe simbolesh. Çdo karakter përveç fundit të rreshtit (n) Çdo karakter nga grupi [^xxx] Çdo karakter përveç karaktereve nga grupi Çdo karakter nga diapazoni ] Zbritja e një grupi ose diapazoni nga një tjetër p(emër) Çdo karakter i specifikuar nga Unicode Emri i kategorisë P (emri) Çdo karakter përveç atyre të specifikuara nga emri i kategorisë Unicode w Grupi i karaktereve të përdorura në përcaktimin e identifikuesve W Grupi i karaktereve që nuk përdoren në përcaktimin e identifikuesve s Hapësirat S Të gjitha përveç hapësirave d Numrat D Jo-shifrore Shembuj : @". +" – "rn. Ka ndy rreshta"; @"+" – "0 xabcfx"; @"[^fx]+" – "0 xabcfx"; @"+" – "0 xabcfx"; @"[^a-f]+" – "0 xabcfx"; @"]+" – "0 xabcfx"; @"p(Lu)" – "Dritat e qytetit"; // Lu – shkronja të mëdha @"P(Lu)" - "Qytet"; @"p(Is. cirilik)" – "ha. OS"; //Është. Shkronja cirilike - ruse
Programimi i PB Anchor ^, A Në fillim të rreshtit $, Z Në fund të rreshtit ose përpara karakterit "n" në fund të rreshtit z Në fund të rreshtit G Ku përfundon ndeshja e mëparshme b Kufiri i fjalës B Çdo pozicion jo në një kufi fjalësh Shembuj: @ "G(d)" – "(1)(3)(5)(9)"; // tre ndeshje (1), (2) dhe (3) @"bnS*ionb" – "dhurim kombi"; @"Bendw*b" – "fundi dërgon huadhënësin durim".
Programimi i operacioneve RT (kuantifikuesit) *, *? Përsëritje +, +? Përsëritje pozitive? , ? ? Zero apo një ndeshje (n), (n)? Saktësisht n përputhet (n, ), (n, )? Të paktën n ndeshje (n, m), (n, m)? Nga n në m përputhet Shembuj (kuantifikuesit e parë janë të pangopur, kërkojnë sa më shumë elementë, të dytit dembelë, kërkojnë sa më pak elementë): @"d(3, )" – "888 -5555 "; @"^d(3)" - "913 -913"; @"-d(3)$" - "913 -913"; @"5+? 5" - "888 -5555"; // tre ndeshje - 55, 55 dhe 55 @"5+5" - "888 -5555".
Programimi RV Grupimi () Një grup që merr automatikisht një numër (? :) Mos e ruani grupin (?) ose (? "Emri") Nëse gjendet një përputhje, krijohet një grup me emër (?) ose Fshi një të përcaktuar më parë grup dhe (? "emri - emri") duke ruajtur në një grup të ri një nënvarg midis një grupi të përcaktuar më parë dhe një grupi të ri (? imnsx:) Aktivizon ose çaktivizon ndonjë nga pesë (? –imnsx:) opsionet e mundshme në një grup: i – e pandjeshme ndaj rasteve; s – një rresht (pastaj “.” është çdo karakter); m - mënyra me shumë rreshta ("^", "$" - fillimi dhe fundi i çdo rreshti); n – mos kapni grupe pa emër; x – përjashtoni hapësirat pa ikje nga modeli dhe përfshini komentet pas shenjës së numrit (#) (? =) Një deklaratë paraprake pozitive me gjatësi zero
Programimi RT (? !) Deklaratë e parashikimit me gjatësi zero negative (?) Pjesë e pakthyeshme (e pangopur) e një shprehjeje Shembuj: @"(an)+" – "banane anale"; @"an+" – "analet e bananeve"; // krahaso, tri ndeshje - an, an dhe ann @"(? i: an)+" - "ba. NAnas analet"; @"+(? =d)" – "abc xyz 12 555 w"; @"(?
Src="https://site/presentation/-112203859_437213351/image-24.jpg" alt="RV Programimi i lidhjeve numri Lidhja me grupin k Lidhja me grupin e emërtuar Shembuj: @"> Программирование РВ Ссылки число Ссылка на группу k Ссылка на именованную группу Примеры: @"(w)1" – "deep"; @"(? w)k " – "deep". Конструкции изменения | Альтернатива (соответствует операции объединения) (? (выражение)да|нет) Сопоставляется с частью «да» , если выражение соответствует; в противном случае сопоставляется с необязательной частью «нет» (? (имя)да|нет), Сопоставляется с частью «да» , если названное имя (? (число)да|нет) захвата имеет соответствие; в противном случае сопоставляется с необязательной частью «нет» Пример: @"th(e|is|at)" – "this is the day";!}
Programimi i Zëvendësimeve RV $number Zëvendëson pjesën e vargut që korrespondon me grupin me numrin e specifikuar $(emri) Zëvendëson pjesën e vargut që korrespondon me grupin me emrin e specifikuar $$ Zëvendëson $ $& Zëvendëson me një kopje të plotë match $` Zëvendëson tekstin e vargut të hyrjes derisa të përputhet me $" Zëvendëson tekstin e rreshtave të hyrjes pas ndeshjes $+ Zëvendëso grupin e fundit të kapur $_ Zëvendëso të gjithë rreshtin Komente (? #) Komenti në linjë # Koment në fund të rreshtit
Programimi RT Rezultatet e Regex: Regex Matches() Match. Grupet e Përputhjes së Koleksionit () Grupi. Kapja e grupit të koleksionit () Kapja. Regjistrimet e koleksionit ()
Shembull programimi RV në C++ CLI (Aplikacioni Visual C++/CLR/CLR konsol): int main() ( Regex ^r = gcnew Regex(L"((\d)+)+"); Përputhje ^m = r-> Përputhje (L"123 456"); int përputhje. Numër = 0; ndërsa (m-> Sukses) ( Konsola: : Shkruaj. Line(L"Përputhje (0)", ++përputhje. Numërimi); për (int i = 1; i Grupet->Numërimi; i++) ( Grupi ^g = m->Grupet[i]; Konsola: : Shkruani. Linja(L" Grupi (0) = "(1)"", i, g-> Vlera ); për (int j = 0; j Captures->Count; j++) ( Capture ^c = g-> Captures[j]; Console: : Write. Line(L" Capture (0) = "(1)" , pozicioni = (2), gjatësia = (3)", j, c, c->Indeksi, c->Gjatësia); ) ) m = m->Tjetër. Përputhje(); : : E rregullt. Shprehjet
Aktivizimi i veprimeve dhe gjetja e gabimeve Kufizimi i numrit të shifrave domethënëse në një numër: (s + e)(pd+ + d+(pd* + e)) s = +|p = . d = d s + e = s? = (+|-)? pd* + e = (pd*)? = (.d*)? @"(+|-)? (. d+|d+(. d*)?)" ose @"^(+|-)? (. d+|d+(. d*)?)$" Regex r = Regex i ri (@"^(+|-)? (. (? "shifror"d)+|(? "shifror"d)+(. (? "shifror"d)*)?)$"); Ndeshje m = r. Përputhje ("+1. 23456789"); nëse (m. Sukses) (Grupi g = m. Grupet["shifror"]; nëse (g. Kapet. Numri
Aktivizimi i veprimeve dhe gjetja e gabimeve Përcaktimi i pozicionit të gabimit: Regex r = new Regex(@"(+|-)? (. (? "shifror"d)+|(? "shifror"d)+(. (? "shifror" d)*)?)"); string str = "+1. 2345!678"; Ndeshje m = r. Ndeshje (rr); if (m. Sukses) ( Grupi g = m. Grupet["shifror"]; nëse (g. Kap. Numërimi 0) Konsola. Shkruaj. Line("Gabim në pozicionin 1: karakter i papritur "(0)"", str ), përndryshe nëse (m. Gjatësia
Mundësimi i veprimeve dhe kërkimi i gabimeve Përcaktimi i pozicionit të gabimit: 1. pozicioni i parë i zinxhirit të hyrjes (1), nëse përputhja e parë nuk fillon nga pozicioni Indeksi = 0; 2. pozicioni pas ndeshjes së fundit (ndeshja. Gjatësia + 1), nëse nuk përputhet me pozicionin e fundit të zinxhirit të hyrjes; 3. pozicioni i hendekut të parë ndërmjet ndeshjeve (ndeshja[i]. Indeksi + përputhja[i]. Gjatësia + 1), nëse karakteri që ndjek ndeshjen e mëparshme nuk është karakteri i parë i ndeshjes së ardhshme.
Indeksi) pushim; indeksi = m[i]. Indeksi + m[i]. Gjatësia; ) Konsol. Shkruaj. Line("Gabim në pozicionin (0) "(1)"", indeksi + 1, str); ) "abc. xyz. pqr" – e saktë; "+abc. xyz. pqr” – gabim në pozicionin 1 (“+”); "abc. xyz. pqr! – gabim në pozicionin 12 (“!”); "abc. xyz!. pqr" – gabim në pozicionin 8 (“!”).
Aktivizimi i veprimeve dhe kërkimi i gabimeve Por! "abc. xyz. +pqr” – gabim në pozicionin 8 (“”). Opsioni i ri i shabllonit: @"w+(. w+)*(. (? !$))? " Vleresimi: "abc. xyz. +pqr” – gabim në pozicionin 9 (“+”); "abc. xyz. pqr. " – gabim në pozicionin 12 (".").
Përkufizime të balancuara: "(? "x")" shton një element në koleksionin e quajtur "x"; "(? "-x")" heq një element nga koleksioni "x"; "(? (x)(? !))" kontrollon që nuk ka mbetur asnjë element në koleksionin "x". Gjuha L që përshkruan operatorët e mbivendosur të Pascal-it “fillon fundi; ": @"^s*((? "fillon+)+(? "-fillimi"mbaron*; s*)+)*(? (fillimi)(? !))$".
Është më i përshtatshëm për të përshkruar fjalorin e një gjuhe në formën e shprehjeve të rregullta dhe për të njohur gjuhën duke përdorur CA. Prandaj, është e rëndësishme të jeni në gjendje të konvertoni përkufizimet gjuhësore në formën e shprehjeve të rregullta në një përkufizim në formën e një CA. Ky transformim u propozua nga Kenneth Thompson.
Makina e gjendjes së fundme është pesë (S, S, d, S 0, F)
S është një grup i fundëm i gjendjeve.
S është një grup i kufizuar sinjalesh hyrëse të vlefshme.
d - funksioni i tranzicionit. Ai pasqyron bashkësinë Sx(SÈ(e)) në bashkësinë e gjendjeve të një automati të fundëm jo-përcaktues. Për një automat determinist, funksioni i tranzicionit pasqyron grupin SxS në grupin e gjendjeve automatike. Me fjalë të tjera, në varësi të gjendjes dhe simbolit të hyrjes, d përcakton gjendjen e re të makinës.
S 0 - gjendja fillestare e automatit të fundëm, S 0 О S.
F është bashkësia e gjendjeve përfundimtare të automatit, F О S.
Funksionimi i një makine me gjendje të fundme është një sekuencë hapash. Hapi përcaktohet nga gjendja e makinës dhe simboli i hyrjes. Vetë hapi konsiston në ndryshimin e gjendjes së makinës dhe leximin e simbolit tjetër të sekuencës hyrëse.
Ekzistojnë rregullat e mëposhtme për konvertimin e shprehjeve të rregullta në një makinë shtetërore.
1 Shprehja e rregullt "e" shndërrohet në një automat të dy gjendjeve dhe një kalim elektronik midis tyre (Figura 1).
Figura 1. – Makinë automatike për e-transition
2 Një shprehje e rregullt nga një karakter "a" konvertohet në një automat të fundëm të dy gjendjeve dhe një kalim ndërmjet tyre bazuar në sinjalin hyrës a (Figura 2).
Figura 2. – Makinë automatike për lëvizje me simbol a
3 Le të ketë një shprehje të rregullt rs dhe makinat e gjendjes së fundme për shprehjen r dhe shprehja s janë ndërtuar tashmë. Pastaj dy makina lidhen në seri. Figura 3 tregon automatet origjinale për gjuhët r dhe s. Figura tregon një automat për njohjen e lidhjes së këtyre gjuhëve.
Makinë për r Makinë për s
Figura 3. – Automata fillestare
Figura 4. – Makina e lidhjes së gjuhës
4 Le të ketë një shprehje të rregullt r | s dhe makinat e gjendjes së fundme janë ndërtuar tashmë për shprehjen r dhe shprehjen s (Figura 3). Atëherë automati që rezulton duhet të ketë një alternativë ndaj ekzekutimit të njërës nga dy automatet. Domethënë, një automat për shprehjen r | s për automatet për r dhe s nga Figura 3 ka formën e treguar në Figurën 5.
Figura 5. – Makinë automatike për kombinimin e gjuhëve
5 Le të ketë një shprehje të rregullt r* për automatikun e fundëm të ndërtuar r. Në këtë rast, futen dy gjendje të reja për të bërë të mundur anashkalimin e shprehjes automaton r, dhe gjithashtu prezantojnë një kalim elektronik midis gjendjeve përfundimtare dhe fillestare për të bërë të mundur përsëritjen e automatit r disa herë. Nëse për shprehjen e rregullt r ndërtohet një automat i ngjashëm me Figurën 3, atëherë shprehja e rregullt r* korrespondon me automatin e fundëm të paraqitur në Figurën 6.
Cilësimet
Sipas teoremës së Kleene, çdo shprehje e rregullt ju mund të lidhni një makinë të fundme, e cila është një model formal i algoritmit për njohjen e leksemave të shënuara me një shprehje të rregullt të caktuar. Në termat më të përgjithshëm, një makinë shtetërore-Njohësi përcaktohet nga një grup i kufizuar i gjendjeve karakteristike të rrymës hyrëse dhe kalimeve ndërmjet tyre. Një ndryshim i gjendjes ndodh kur simbolet e rrymës hyrëse merren nga një alfabet i caktuar në përputhje me funksionin e tranzicionit, i cili përcakton gjendjet e mundshme pasuese bazuar në simbolin hyrës dhe gjendjen aktuale. Ndër gjendjet e mundshme spikat ajo fillestare(fillestare) dhe përfundimtare(duke lejuar) gjendjet në të cilat njohësi i fundëm i automatit mund të jetë, përkatësisht, në fillim dhe në përfundim të përpunimit të shenjave të rrymës hyrëse. Nëse sekuenca hyrëse e simboleve mund të gjenerojë një sekuencë tranzicioni që mund të transferojë makinën e gjendjes së fundme nga gjendja fillestare në një nga gjendjet përfundimtare, atëherë ajo konsiderohet e pranueshme dhe i përket grupit të rregullt të njohur prej tij.
(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
Tabela 1
| 0 | 1 | |
| Q1 | Q4 | Q2 |
| Q2 | Q3 | Q1 |
| Q3 | Q2 | Q4 |
| Q4 | Q1 | Q3 |
Kolonat e tabelës së tranzicionit tregojnë karakteret e alfabetit të hyrjes, dhe rreshtat korrespondojnë me gjendjet aktuale të DFA. Elementet e secilës rresht tregojnë gjendjet e DFA, në të cilën duhet të kalojë nga gjendja aktuale me marrjen e karaktereve përkatëse të alfabetit të hyrjes. Në veçanti, nga rreshti i parë i kësaj tabele të tranzicionit rrjedh se marrja e simboleve 0 dhe 1 në gjendjen fillestare Q1 përkthen DFA për shtetet Q4 dhe Q2, respektivisht.
Kur njeh një sekuencë hyrëse duke përdorur tabelën e tranzicionit, është e lehtë të gjurmosh ndryshimet në gjendjen e DFA në mënyrë që të përcaktohet nëse një nga gjendjet lejuese është arritur apo jo. Në veçanti, për vektorin binar 01001000 me një numër çift zero dhe njësh, DFA e konsideruar gjeneron sekuencën e mëposhtme të tranzicioneve, ku çdo tranzicion është etiketuar me simbolin e alfabetit të hyrjes që e shkakton atë:
Q1 0 Q4 1 Q3 0 Q2 0 Q3 1 Q4 1 Q1 0 Q4 0 Q1
Kjo sekuencë e tranzicionit përfundon me gjendjen pranuese Q1, prandaj, vektori binar 01001000 i përket grupit të rregullt të njohur nga DFA e konsideruar dhe plotëson shprehjen e rregullt të mësipërme.
Si përfundim, duhet theksuar se metoda joformale e konsideruar e ndërtimit
Për studimin e mëtejshëm të vetive të automatave të fundme dhe, në veçanti, për zgjidhjen e problemit të sintezës, teorema e mëposhtme është e rëndësishme.
Teorema 7.7 (teorema e përcaktimit). Për çdo automat të fundëm, mund të ndërtohet një automat i fundëm përcaktues ekuivalent.
Për të vërtetuar teoremën, është e nevojshme, së pari, të përshkruhet algoritmi për ndërtimin e një automati të fundëm përcaktues nga ai origjinal; së dyti, për të justifikuar këtë algoritëm duke vërtetuar me rigorozitet se ai vërtet prodhon një makinë gjendjeje që është përcaktuese dhe ekuivalente me atë origjinale. Këtu paraqesim vetëm algoritmin për ndërtimin e një automati deterministik.
Shndërrimi i një automati të fundëm arbitrar në një përcaktues ekuivalent kryhet në dy faza: së pari hiqen harqet me etiketën \lambda, më pas kryhet vetë përcaktimi.
1. Heqja e tranzicioneve λ (harqet e etiketuara \lambda).
Për të shkuar nga automati origjinal i fundëm M=(V,Q,q_0,F,\delta) në automatin ekuivalent të fundëm M"=(V,Q",q_0,F",\delta") pa λ-tranzicione, ai mjafton në origjinal bëni shndërrimet e mëposhtme në grafikun M.
A. Të gjitha gjendjet, përveç asaj fillestare, në të cilën hyjnë vetëm harqet me etiketën \lambda, fshihen; duke përcaktuar kështu bashkësinë Q" të automatit të fundëm M". Është e qartë se Q"\subseteq Q. Në të njëjtën kohë, supozojmë se gjendja fillestare mbetet e njëjtë.
b. Bashkësia e harqeve të automatit të fundëm M" dhe etiketave të tyre (për rrjedhojë funksioni i tranzicionit M") përcaktohet si më poshtë: për çdo dy gjendje p,r\në Q",~ p\to_(a)r ndodh nëse dhe vetëm nëse a \ në V , dhe në grafikun M vlen një nga dy gjërat: ose ka një hark nga p në r, etiketa e të cilit përmban simbolin a, ose ka një gjendje q të tillë që p\Rightarrow_(\lambda)^( +)q dhe q\ to_(a)r Në këtë rast, kulmi q, në përgjithësi, mund të mos i përkasë bashkësisë Q", d.m.th. ai mund të zhduket kur kalon në automatin M" (Fig. 7.11). Nëse q\in Q" , atëherë, natyrisht, harku (q,r) do të ruhet në M" dhe simboli a do të jetë një nga simbolet që i përket etiketës së këtij harku (Fig. 7.12).
Kështu, në M" ruhen të gjithë harqet M, etiketat e të cilëve janë të ndryshëm nga \lambda dhe që lidhin një çift (kulme) gjendjesh nga bashkësia Q" (jo të fshirë sipas pjesës a). Përveç kësaj, për çdo treshe të gjendjeve p,q,r (jo domosdoshmërisht të ndryshme!), të tilla që p,r\in Q" dhe ekziston një shteg me gjatësi jozero nga p në q, etiketa e së cilës është e barabartë te \lambda (d.m.th. shtegu sipas kalimeve λ), dhe një hark të çon nga q në r, etiketa e të cilit përmban simbolin a të alfabetit të hyrjes, në M" ndërtohet një hark nga p në r, etiketa e i cili përmban simbolin a (shih Fig. 7.11).
V. Bashkësia e gjendjeve përfundimtare F" të automatit të fundëm M" përmban të gjitha gjendjet q\në Q", d.m.th. gjendjet e automatit të fundëm M që nuk fshihen sipas paragrafit a, për të cilat q\Rightarrow_(\lambda)^(\ ast) mban q_f për disa q_f\in F (d.m.th. ose gjendja q në vetvete është gjendja përfundimtare e automatit të fundëm M, ose një shteg me gjatësi jo zero të çon prej tij përgjatë harqeve të etiketuar \lambda në një nga gjendjet përfundimtare të automati i fundëm M) (Fig. 7.13) .
2. Vetë përcaktimi.
Le të jetë M=(Q,V,q_0,F,\delta) një automat i fundëm pa λ-tranzicione. Le të ndërtojmë një automat të fundëm përcaktues M_1 ekuivalent me M.
Ky automat i fundëm është përcaktuar në atë mënyrë që bashkësia e gjendjes së tij është bashkësia e të gjitha nënbashkësive të grupit të gjendjes së automatit të fundëm M. Kjo do të thotë që çdo gjendje individuale e automatit të fundëm M_1 përcaktohet si një nëngrup i caktuar i grupit të gjendjeve të automatit të fundëm M. Në këtë rast, gjendja fillestare e makinës së re të gjendjes së fundme (d.m.th. M_1) është një nëngrup njëtonësh që përmban gjendjen fillestare të makinës së vjetër të gjendjes së fundme (d.m.th. M), dhe gjendjet përfundimtare të makinës së re të gjendjes së fundme janë të gjitha nënbashkësi të tilla Q që përmbajnë të paktën një kulm përfundimtar të automatit origjinal të fundëm M.
Tani e tutje, duke lejuar njëfarë lirie të fjalës, ne ndonjëherë do t'i quajmë gjendjet e automateve të fundme M_1 gjendje-bashkësi. Sidoqoftë, është e rëndësishme të kuptohet qartë se çdo grup i tillë gjendjesh është një gjendje e veçantë e një automati të ri të fundëm, por jo një grup i gjendjeve të tij. Në të njëjtën kohë, për automatikun e fundëm origjinal ("të vjetër") M ky është pikërisht grupi i gjendjeve të tij. Në mënyrë figurative, çdo nëngrup i gjendjeve të automatit të vjetër të fundëm "kolapsohet" në një gjendje të automatit të ri të fundëm*.
*Formalisht, ne duhet të përcaktojmë grupin Q_1 si një grup që është në korrespondencë një-me-një me grupin 2^Q, por është akoma më e përshtatshme për ne të supozojmë se Q_1 përkon me 2^Q - në fund të fundit, grup i gjendjeve të një automati të fundëm mund të jetë çdo grup i fundëm jo bosh.
Funksioni i tranzicionit i automatit të ri të fundëm është përcaktuar në mënyrë që nga grupi i gjendjes S me simbolin hyrës a, automati i fundëm M_1 shkon në bashkësinë e gjendjes, që është bashkimi i të gjitha grupeve të gjendjeve të automatit të vjetër të fundëm në të cilin ky automat i vjetër i fundëm shkon me simbolin a nga çdo grup gjendjesh S. Kështu, automati i fundëm M_1 është determinist nga ndërtimi.
Përshkrimi verbal i mësipërm mund të përkthehet në formula si më poshtë: ne ndërtojmë një makinë të fundme M_1 në mënyrë që
M_1=(Q_1,V,\(q_0\),F_1,\delta_1) , ku
\fillim(rastet)Q_1=2^Q,\katër F_1=\(T\colon\, T\cap F\ne\varnothing,~T\in2^Q\),\\ (\për të gjithë S\nënsetek Q) (\përgjithësisht a\in V)\Bigl(\delta_1(S,a)= \bigcup\limits_(q\in S)\delta(q,a)\Bigr). \fund (rastet)
Le t'i kushtojmë vëmendje faktit se midis gjendjeve të automatit të ri të fundëm ekziston një gjendje \varnothing , dhe, sipas (7.8), \delta_1(\varnothing,a)=\varnothing për çdo simbol hyrës a . Kjo do të thotë që, pasi të jetë në një gjendje të tillë, makina shtetërore M_1 nuk do ta lërë atë. Në përgjithësi, çdo gjendje q e një automati të fundëm e tillë që për çdo simbol hyrës a kemi \delta(q,a)=q quhet gjendje absorbuese e automatit të fundëm. Kështu, gjendja \varnothing e makinës përcaktuese të gjendjes së fundme M_1 është thithëse. Është gjithashtu e dobishme të theksohet se \delta_1(S,a)=\varnothing nëse dhe vetëm nëse për çdo q\in S (gjendjet e makinës së vjetër të gjendjes së fundme nga bashkësia e gjendjeve S ) \delta(q,a)= \varnothing, d.m.th. në grafikun M, asnjë hark nuk del nga çdo gjendje e tillë q, e shënuar me simbolin a.
Mund të vërtetohet se automati i fundëm i marrë duke përdorur një algoritëm të tillë është i barabartë me atë origjinal.
Shembulli 7.9. Le të përcaktojmë automatikun e fundëm të paraqitur në Fig. 7.14.
Një automat ekuivalent i fundëm pa kalime λ është paraqitur në Fig. 7.15. Vini re se kulmi q_2 zhduket, pasi vetëm harqet "bosh" hyjnë në të.
Për të përcaktuar automatikun që rezulton, nuk është aspak e nevojshme të shënohen të gjitha gjendjet e tij 2^3=8, shumë prej të cilave mund të mos jenë të arritshme nga gjendja fillestare \(q_0\) . Për të marrë gjendjet që janë të arritshme nga \(q_0\), dhe vetëm ato, ne do të përdorim të ashtuquajturën metodë tërheqjeje.
Kjo metodë në përgjithësi mund të përshkruhet si më poshtë.
Në automatin fillestar të fundëm (pa harqe boshe) përcaktojmë të gjitha grupet e gjendjeve që janë të arritshme nga ajo fillestare, d.m.th. për çdo simbol hyrës a gjejmë bashkësinë \delta(q_0,a) . Çdo grup i tillë në automatin e ri është një gjendje e aksesueshme drejtpërdrejt nga ajo fillestare.
Për secilin nga grupet e përcaktuara të gjendjes S dhe çdo simbol hyrës a, gjejmë grupin \textstyle(\mathop(\bigcup\limits_(q\in S) \delta(q,a))\limits^(\phantom( A)^( .))) . Të gjitha gjendjet e marra në këtë hap do të jenë gjendje të një automati të ri (përcaktues), i arritshëm nga kulmi fillestar përgjatë një shtegu me gjatësi 2. Ne përsërisim procedurën e përshkruar derisa të mos shfaqen gjendje të reja të grupit (përfshirë atë bosh!). Mund të tregohet se kjo prodhon të gjitha gjendjet e automatit të fundëm M_1 që janë të arritshme nga gjendja fillestare \(q_0\) .
Për makinën e gjendjes së fundme në Fig. 7.15 kemi:
\fillim(përafruar)& \delta_1(\(q_0\),a)=\(q_1\);\qquad \delta_1(\(q_0\),b)=\(q_1,q_3\);\\ & \ delta_1(\(q_1\),a)=\(q_1\);\qquad \delta_1(\(q_1\),b)=\(q_1\);\\ & \delta_1 (\(q_1,q_3\) ,a)= \delta(q_1,a)\kup \delta(q_3,a)= \(q_1\)\kup\(q_1\)=\(q_1\);\\ & \delta_1(\(q_1, q_3\),b)= \delta(q_1,b)\kup \delta(q_3,b)= \(q_1\)\kup\(q_1\)=\(q_1\). \fund (të rreshtuar)
Meqenëse nuk janë shfaqur grupe të reja gjendjesh, procedura e "tërheqjes" përfundon këtu dhe marrim grafikun e paraqitur në Fig. 7.16.
Shtimi i rregullt i gjuhësNjë nga pasojat e rëndësishme teorike të teoremës së përcaktimit është teorema e mëposhtme.
Teorema 7.8. Plotësuesi i një gjuhe të rregullt është një gjuhë e rregullt.
Le të jetë L një gjuhë e rregullt në alfabetin V. Atëherë plotësuesi i gjuhës L (si grup fjalësh) është gjuha \overline(L)=V^(\ast)\setminus L .
Sipas teoremës 7.7, për një gjuhë të rregullt L, mund të ndërtohet një automat i fundëm përcaktues M që pranon L. Meqenëse në një automat përcaktues nga çdo kulm për çdo simbol hyrës përcaktohet një kalim në saktësisht një kulm, çfarëdo që të jetë zinxhiri x në alfabetin V, ekziston një shteg unik për të në M, duke filluar në gjendjen fillestare në të cilën lexohet zinxhiri x. Është e qartë se zinxhiri x lejohet nga automati M , pra x\in L(M) , nëse dhe vetëm nëse gjendja e fundit e shtegut të specifikuar është përfundimtare. Nga kjo rrjedh se zinxhiri x\notin L(M) nëse dhe vetëm nëse gjendja e fundit e shtegut të specifikuar nuk është përfundimtare. Por ne kemi nevojë vetëm për një automat të fundëm M" që pranon një zinxhir x nëse dhe vetëm nëse nuk lejohet nga automati origjinal i fundëm M. Prandaj, duke e kthyer çdo gjendje përfundimtare të M në një gjendje jo-përfundimtare dhe anasjelltas, marrim një automat përcaktues që pranon shtimin e gjuhës L .
Teorema e provuar na lejon të ndërtojmë një automat të fundëm që nuk pranon një grup të caktuar zinxhirësh, duke përdorur metodën e mëposhtme: ne fillimisht ndërtojmë një automat që pranon një grup të caktuar zinxhirësh, më pas e përcaktojmë dhe shkojmë në automat për mbledhje si treguar në vërtetimin e Teoremës 7.8.
Shembulli 7.10. A. Le të ndërtojmë një automat të fundëm që pranon të gjithë zinxhirët në alfabetin \(0;1\) përveç zinxhirit 101.
Së pari, le të ndërtojmë një automat të fundëm që lejon një zinxhir të vetëm 101. Ky automat është paraqitur në Fig. 7.17.
Ky automat është pothuajse determinist, por jo determinist, pasi nuk është plotësisht i përcaktuar. Le ta përcaktojmë atë dhe të marrim një automat të fundëm ekuivalent deterministik të paraqitur në Fig. 7.18.
Dhe së fundi, duke kaluar te shtesa (dhe duke riemërtuar gjendjet), marrim automatikun e treguar në Fig. 7.19.
Vini re se në automatikun që rezulton të gjitha kulmet, përveç kulmit s_3, janë përfundimtare.
Vini re gjithashtu se kalimi në komplement, i cili diskutohet në vërtetimin e Teoremës 7.8, mund të kryhet vetëm në një automat determinist. Nëse do të ndërronim rolet e kulmeve përfundimtare dhe jo-përfundimtare në automatin e paraqitur në Fig. 7.17, atëherë do të merrnim një automat që pranon gjuhën \(\lambda,1,10\) , e cila nuk është - siç mund të imagjinohet lehtësisht - grupi i të gjithë zinxhirëve përveç zinxhirit 101.
Vini re gjithashtu se makina e gjendjes së fundme në Fig. 7.19 lejon të gjitha vargjet që përmbajnë një dukuri të vargut 101, por që nuk përputhen me atë varg. Këtu, për shembull, është shtegu që mban zinxhirin 1011: s_0,s_1,s_2,s_3,t.
b. Le të ndërtojmë një automat të fundëm që pranon të gjithë zinxhirët në alfabetin \(0;1\) përveç atyre që përmbajnë një ndodhi të zinxhirit 101. Konsideroni një gjuhë L, çdo zinxhir i së cilës përmban një ndodhi të zinxhirit 101. Mund të jetë përcaktuar si më poshtë:
L=(0+1)^(\ast)101(0+1)^(\ast).
Duhet të ndërtojmë një automat për të plotësuar gjuhën L.
Në këtë rast, duke përdorur drejtpërdrejt shprehjen e rregullt, është e lehtë të ndërtohet një automat i fundëm që pranon gjuhën L (Fig. 7.20).
Pastaj ne do të kryejmë përcaktimin duke përdorur metodën "tërheq". Rezultati i përcaktimit është paraqitur në Fig. 7.21.
Për të zgjidhur plotësisht problemin, gjithçka që mbetet është në Fig. 7.21 këmbejnë rolet e kulmeve përfundimtare dhe jopërfundimtare (Fig. 7.22).
V. Le të diskutojmë idenë e ndërtimit të një automati të fundëm që lejon ata dhe vetëm ata zinxhirë në alfabetin \(0;1\) që nuk fillojnë me zinxhirin 01 dhe nuk përfundojnë me zinxhirin 11 (d.m.th., zinxhirët e forma 01x dhe zinxhirët e tipit y11 nuk lejohen, pavarësisht nga vargjet e tyre ishin x,y\in\(0;1\) ).
Në këtë rast, plotësuesi i gjuhës për të cilën është e nevojshme të ndërtohet një automat i fundëm është bashkësia e të gjithë zinxhirëve të tillë zero dhe njësh që fillojnë me zinxhirin 01 ose përfundojnë me zinxhirin 11. Një automat që lejon këtë grup të zinxhirët janë ndërtuar si një automat për kombinimin e 01(0+1)^(\ ast)+(0+1)^(\ast)11 në të njëjtën mënyrë siç përshkruhet në vërtetimin e teoremës së Kleene (shih Teoremën 7.6).
Nga vetia që klasa e gjuhëve të rregullta është e mbyllur në lidhje me plotësimin (shih Teoremën 7.8) rrjedh menjëherë se kjo klasë është e mbyllur në lidhje me ndryshimin e kryqëzimit, teorisë së grupeve dhe simetrike.
Përfundimi 7.3. Për çdo dy gjuhë të rregullta L_1 dhe L_2 pohimet e mëposhtme janë të vërteta:
1) kryqëzimi i L_1\cap L_2 është i rregullt;
2) diferenca L_1\setminus L_2 është e rregullt;
3) ndryshimi simetrik L_1\vartrekëndëshi L_2 është i rregullt.
Vlefshmëria e deklaratave rrjedh nga identitetet:
\fillim(përafruar) &(\scriptstyle(\mathsf(1)))\quad L_1\cap L_2= \overline(\overline(L_1) \cup\overline(L_2))\,;\\ &(\scriptstyle (\mathsf(2)))\quad L_1\setminus L_2= L_1\cap \overline(L_2)\,;\\ &(\scriptstyle(\mathsf(3))))\quad L_1\,\trekëndësh\ ,L_2 = (L_1\filxhan L_2)\setminus (L_1\kapak L_2).\fund (lidhur)
Së pari, rezultatet e marra na lejojnë të pohojmë se klasa e gjuhëve të rregullta në lidhje me operacionet e bashkimit, kryqëzimit dhe mbledhjes është një algjebër Boolean, në të cilën njësia është gjuha universale dhe zeroja është gjuha boshe. Së dyti, këto veti algjebrike të familjes së gjuhëve të rregullta na lejojnë të zgjidhim problemin e rëndësishëm të njohjes së ekuivalencës së dy automateve të fundme arbitrare.
Sipas përkufizimit 7.10, makinat me gjendje të fundme janë ekuivalente nëse gjuhët që pranojnë janë të njëjta. Prandaj, për të verifikuar ekuivalencën e automatëve M_1 dhe M_2, mjafton të vërtetohet se ndryshimi simetrik i gjuhëve L(M_1) dhe L(M_2) është bosh. Për ta bërë këtë, nga ana tjetër, mjafton të ndërtoni një automat që pranon këtë ndryshim dhe të siguroheni që gjuha që pranon të jetë bosh. Në përgjithësi, problemi i njohjes se gjuha e një makine shtetërore është bosh quhet problemi i zbrazëtisë së makinës shtetërore. Për të zgjidhur këtë problem, mjafton të gjejmë grupin e gjendjeve përfundimtare të automatit që janë të arritshme nga gjendja fillestare. Meqenëse një makinë me gjendje të fundme është një grafik i drejtuar, ky problem mund të zgjidhet, për shembull, duke përdorur kërkimin e parë në gjerësi. Një gjuhë e lejuar nga një makinë me gjendje të fundme është bosh nëse dhe vetëm nëse grupi i gjendjeve përfundimtare të arritshme nga gjendja fillestare është bosh. Në praktikë, preferohet të njihet ekuivalenca e automateve të fundme duke përdorur një algoritëm minimizimi, por tani është e rëndësishme për ne të theksojmë se mundësia themelore e zgjidhjes së problemit të ekuivalencës rrjedh nga teorema 7.7 dhe pasojat e saj algjebrike.
