Automatų teorijos taisyklingos kalbos apibrėžimas. Įprastų kalbų nustatymo metodai. Abėcėlė, žodis, kalba

Laboratorinis darbas Nr.3

Leksinio analizatoriaus kūrimas yra gana paprastas, jei naudojama įprastų kalbų ir baigtinių automatų teorija. Pagal šią teoriją to paties tipo leksemų klasės laikomos formaliosiomis kalbomis (identifikatorių kalba, konstantų kalba ir kt.), kurių sakinių rinkinys aprašomas naudojant atitinkamą generatyvinę gramatiką. Be to, šios kalbos yra tokios paprastos, kad jas generuoja paprasčiausia gramatika – įprasta gramatika.

1 apibrėžimas. generatyvinė gramatika G = , kurių taisyklės turi tokią formą: A::=aB arba C::=b, kur A, B, C Є N; a, b Є Т vadinamas reguliariu (automatiniu).

Kalba L (G), kurią sukuria automatinė gramatika, vadinama automatine (įprastine) kalba arba kalba su baigtiniu skaičiumi būsenų.

1 pavyzdys. Identifikatorių klasė, jei identifikatorius yra seka, susidedanti iš raidžių ir skaičių, o pirmasis identifikatoriaus simbolis gali būti tik raidė, aprašoma tokia generatyvine reguliaria gramatika G = , kuriame

N = (I, K), T = (b, c), S = (I),

P = ( 1. I::= b

Čia b, c yra apibendrinti terminalo simboliai, skirti atitinkamai žymėti raides ir skaičius.

Identifikatoriaus „bbcbc“ generavimo procesas aprašomas tokia pakeitimų seka

I => bbc => bbc => bbcK => bbcbK => bbcbc

Tačiau pagrindinis LA uždavinys – ne leksinių vienetų generavimas, o jų atpažinimas. Taisyklingos kalbos atpažinimo proceso matematinis modelis yra skaičiavimo įrenginys, vadinamas baigtinių būsenų mašina (FA). Terminas „ribinis“ pabrėžia, kad skaičiavimo įrenginys turi fiksuotą ir baigtinį atminties kiekį ir apdoroja įvesties simbolių seką, priklausančią kokiai nors baigtinei aibei. Yra įvairių KA tipų, jei KA išvesties funkcija (darbo rezultatas) yra tik nuoroda, ar įvesties simbolių seka priimtina ar ne, tokia KA vadinama galutinis sprendėjas.

2 apibrėžimas. Šie penki vadinami baigtiniu automatu:

A = , kur V = (a 1 , a 2 , …, a m ) – įvesties abėcėlė (baigtinė simbolių rinkinys);

Q = (q 0 , q 1 , …, q n -1 ) – būsenų abėcėlė (baigtinė simbolių rinkinys);

δ: Q ×V →Q – perėjimo funkcija;

q 0 Є Q – baigtinio automato pradinė būsena;

F Є Q – galutinių būsenų rinkinys.

Erdvėlaivio veikimo schema.

Yra begalinė juosta, padalinta į langelius, kurių kiekvienoje gali būti po vieną simbolį iš V. Ant juostos parašyta grandinėlė α Є V*. Langeliai grandinės kairėje ir dešinėje yra tušti. Yra galutinis valdymo įtaisas (FCU) su skaitymo galvute, kuri gali nuosekliai nuskaityti simbolius iš juostos, judant juosta iš kairės į dešinę. Šiuo atveju valdymo blokas gali būti bet kurios vienos būsenos nuo Q. Valdymo blokas visada pradeda savo darbą pradinėje būsenoje q 0 ir baigiasi vienoje iš galutinių būsenų F. Kiekvieną kartą, pereinant į naują langelį juosta, valdymo blokas pereina į naują būseną pagal funkciją δ.

Erdvėlaivio perėjimo funkciją galima pavaizduoti šiais būdais:

· Komandų rinkinys;

· Būsenos diagrama;

· Pereinamoji lentelė.

Būsenos mašinos komanda parašyta taip:

(q i, a j) → q k, kur q i, q k Є Q; a j Є V.

Ši komanda reiškia, kad būsenos mašina yra q i būsenoje, nuskaito simbolį a j iš juostos ir pereina į būseną q k.

Grafiškai komanda pavaizduota kaip grafiko lankas, einantis nuo viršūnės q i iki viršūnės q k ir pažymėtas įvesties abėcėlės simboliu a j:

Grafinis viso atvaizdavimo δ vaizdas vadinamas baigtinės būsenos mašinos būsenos diagrama.

Jei erdvėlaivis atsiduria situacijoje (q i, a j), kuri nėra kairioji jokios komandos pusė, tada jis sustoja. Jei valdymo blokas suskaičiuoja visus juostoje įrašytus grandinės α simbolius ir tuo pačiu pereina į galutinę būseną q r Є F, tada jie sako, kad grandinę α leidžia baigtinės būsenos mašina.

Erdvėlaivio perėjimo lentelė sudaryta taip: matricos stulpeliai atitinka simbolius iš įvesties abėcėlės, eilutės atitinka simbolius iš būsenos abėcėlės, o matricos elementai atitinka būsenas, į kurias erdvėlaivis pereina tam tikram įvesties simbolio deriniui. ir valstybės simbolis.

Tegul taisyklinga gramatika G = , kurios taisyklės turi tokią formą: A i::= a j A k arba A i::= a j, kur A i, A k Є N ir a j Є T.

Tada baigtinis automatas A = , leidžianti tą pačią kalbą, kurią generuoja įprastinė gramatika G, yra sudaryta taip:

2) Q = N U (Z), Z N ir Z T, Z yra galutinė erdvėlaivio būsena;

5) Atvaizdavimas δ sudaromas tokia forma:

· Kiekviena A i::= a j A k formos gramatikos G pakeitimo taisyklė susieta su komanda (A i, a j) → A k;

· Kiekviena A i::= a j formos pakeitimo taisyklė susieta su komanda (A i, a j) → Z;

2 pavyzdys. Sukurkite gramatikos CA pagal 1 pavyzdį. Turime A = , Kur

1) V = T = (b, c)

2) Q = N U (Z) = (I, R, Z)

3) q 0 = (S) = (I)

5) δ: a) komandų rinkinio pavidalu:

b) būsenos diagramos pavidalu

Yra deterministinės ir nedeterministinės baigtinių būsenų mašinos. Erdvėlaivis vadinamas nedeterministinis KA (NKA), jei jos būsenos diagramoje iš vienos viršūnės kyla keli lankai su vienodais ženklais. Pavyzdžiui, KA iš 2 pavyzdžio yra NKA.

Praktiniais tikslais būtina, kad galutinis atpažinėjas pats nustatytų įvesties simbolių sekos pabaigos momentą ir pateiktų pranešimą apie įvesties sekos teisingumą ar klaidą. Šiuo tikslu įvesties grandinė laikoma apribota dešinėje galo žymekliu ├, o interpretuojamos būsenos įvedamos į erdvėlaivio būsenos diagramą:

Z – „leisti įvesties grandinę“;

O – „įvesties grandinėje buvo prisiminta klaida“;

E – „atmesti įvesties grandinę“.

Būsenos Z ir E yra galutinės, o erdvėlaivis patenka į jas atitinkamai nuskaitęs galutinį žymeklį ├, apdorojęs teisingą arba klaidingą įvesties grandinę. Būsena O yra tarpinė, erdvėlaivis persikelia į ją iš bet kurios galiojančios erdvėlaivio būsenos, kai aptinkama klaida įvesties grandinėje ir lieka ten, kol atkeliauja pabaigos žymeklis ├, po kurio pereina į būseną E – „atmesti įvesties grandinę. “

Tegul L 1 ir L 2 yra kalbos abėcėlėje

Tada, t.y. kalbos sujungimas susideda iš visų pirmosios kalbos žodžių sujungimų su visais antrosios kalbos žodžiais. Visų pirma, jei , tada ir jei , tada .

Įveskime kalbos L „laipsnių“ žymėjimą:

Taigi, L i apima visus žodžius, kuriuos galima suskirstyti į i iš eilės einančius žodžius iš L .

Kalbos L iteraciją (L) * sudaro visi žodžiai, kuriuos iš L galima suskirstyti į kelis iš eilės einančius žodžius:

Jis gali būti pavaizduotas naudojant laipsnius:

Dažnai patogu laikyti „sutrumpintą“ kalbos iteraciją, kurioje nėra tuščio žodžio, jei jo kalboje nėra: . Tai nėra nauja operacija, o tiesiog patogus išraiškos trumpinys.

Taip pat atkreipkite dėmesį, kad jei abėcėlę laikome baigtine kalba, susidedančia iš vienos raidės žodžių, tada anksčiau įvestas visų žodžių, įskaitant tuščią, aibės žymėjimas abėcėlėje atitinka šios kalbos iteracijos apibrėžimą.

Šioje lentelėje pateikiamas formalus indukcinis apibrėžimas reguliarios išraiškos per abėcėlę ir kalbas, kurias jie atstovauja.

Išraiška r	Kalba L r
	L a =(a)
Tegul r 1 ir r 2 yra	L r1 ir L r2 -atstovaujami
reguliarios išraiškos.	jų kalbos.
Tada šios išraiškos
yra reguliarūs	ir atstovauja kalboms:
r=(r 1 +r 2)
r = (r 1 circr 2)
r=(r 1) *	L r = L r1 *

Įrašant reguliarios išraiškos Mes praleisime sujungimo ženklą ir darome prielaidą, kad operacija * turi didesnį prioritetą nei sujungimas ir +, o sujungimas turi didesnį prioritetą nei +. Tai leis praleisti daug skliaustų. Pavyzdžiui, galima parašyti kaip 10(1 * + 0) .

Apibrėžimas 5.1. Du reguliarios išraiškos R ir p laikomi lygiaverčiais, jei jų atstovaujamos kalbos yra tos pačios, t.y. L r = L p . Šiuo atveju rašome r = p.

Nesunku patikrinti, pavyzdžiui, toliau nurodytus dalykus reguliarios savybės operacijos:

• r + p= p+ r (sąjungos komutaciškumas),
• (r+p) +q = r + (p+q) (sąjungos asociatyvumas),
• (r p) q = r (p q) (sujungimo asociatyvumas),
• (r *) * = r * (iteracijos idempotencija),
• (r +p) q = rq + pq(paskirstymas).

5.1 pavyzdys. Įrodykime, kaip pavyzdį, ne tokią akivaizdžią lygybę: (r + p) * = (r * p *) *.

Tegul L 1 yra kalba, pavaizduota jos kairiąja puse, o L 2 – dešine. Tuščias žodis priklauso abiem kalboms. Jei žodis yra netuščias, tai pagal iteracijos apibrėžimą jis gali būti vaizduojamas kaip kalbai priklausančių požodžių junginys. Tačiau ši kalba yra kalbos L"=L r * L p * poaibis (kodėl?). Todėl . Ir atvirkščiai, jei žodis , tai jis pavaizduojamas kaip požodžių, priklausančių kalbai L ", junginys. Kiekvienas iš tokių požodžių v yra atvaizduojamas forma v= v 1 1 ... v k 1 v 1 2 ... v l 2, kur visiems i=1, ... , k yra požodis, o visiems j=1, ... , l yra požodis (gali būti, kad k arba l lygus 0). Bet tai reiškia, kad w yra požodžių junginys, kurių kiekvienas priklauso ir todėl .

Įprasta kalba

Kalbos teorijoje įprastas rinkinys(arba, įprasta kalba) vadinama formalia kalba, kuri atitinka šias savybes. Šios paprastos savybės yra tokios, kad taisyklingųjų aibių klasę patogu tirti kaip visumą, o gauti rezultatai pritaikomi daugeliu svarbių formalių kalbų atvejų. Tai yra, įprastos aibės sąvoka yra matematinės struktūros pavyzdys.

Įprastos aibės apibrėžimas

Tegu Σ yra baigtinė abėcėlė. Įprastas komplektas R(Σ) abėcėlėje Σ apibrėžiamas šiomis rekursinėmis savybėmis:

taip pat žr

• Analizatoriaus kūrimas remiantis automatiniu metodu

Wikimedia fondas. 2010 m.

Pažiūrėkite, kas yra „įprasta kalba“ kituose žodynuose:

įprasta kalba- - Telekomunikacijų temos, pagrindinės sąvokos LT įprastinė kalba... Techninis vertėjo vadovas

- (lot. regularius, iš regula taisyklė). Teisingai, teisingai sutvarkyta, pagaminta. Reguliarus mašinos veikimas. Net insultas. Reguliarus gyvenimas. Teisingas, padorus, monotoniškas gyvenimas. Į rusų kalbą įtrauktų svetimžodžių žodynas.... Rusų kalbos svetimžodžių žodynas

Cm … Sinonimų žodynas

Senovės rašto kalba– Kalba, turinti ilgas rašto tradicijas, tai yra, prieš kelis šimtmečius gavo rašomą, pritaikytą tam tikros kalbos sandarai, o rašytinės kalbos versijos funkcionavimas buvo ne epizodinis, o taisyklingas, su... . .. Sociolingvistinių terminų žodynas

Šis terminas turi kitas reikšmes, žr. kečujų kalba. Kečujų slapyvardis: Qhichwa Simi, Runa Simi Šalys ... Vikipedija

Pastato karkasas su kolonų ar stulpų tinkleliu, paremtu vienodo dydžio laipteliu (bulgarų k.; Български) vienodo skeleto (čekų k.; čeština) pravidelný skeletas (vok.; vok.) regelmäßiges Skelett (vengr.; magyar) ... ... Statybos žodynas

- [PRANCŪZIJOS PARKAS] parkas, turintis geometriškai taisyklingą išplanavimą, dažniausiai ašinį (bulgarų k.; Български) frenski park (ček.; Čeština) francouzský park (vok.; vok.) regelmäßiger Park; Französischer parkas… Statybos žodynas

Kečujų pavardė: Qhichwa Simi, Runa Simi Šalys: Argentina, Bolivija, Kolumbija, Peru, Čilė, Ekvadoras Regionai: Andai Oficialus statusas: Peru ... Wikipedia

Tagalogų kalba- (tagal, tagala, tagalo; tagalog) viena iš Filipinų kalbų. Pradinio paskirstymo sritis yra politiškai, ekonomiškai ir kultūriškai svarbiausiame Filipinų Respublikos regione – centrinėje ir pietinėje salos dalyse... ... Kalbinis enciklopedinis žodynas

Knygos

• Išvestiniai veiksmažodžiai. Suomių kalbos gramatikos paslaptys. Vadovėlis, Safronov V.D.. Vadovas skirtas vienam įdomiausių ir nepakankamai pateiktų suomių kalbos gramatikos skyrių rusų kalba mokomojoje literatūroje – išvestiniams veiksmažodžiams. Jie susidaro iš veiksmažodžių ir iš vardų...