Definicija običajnega jezika teorije avtomatov. Metode za določanje običajnih jezikov. Abeceda, beseda, jezik

Laboratorijsko delo št. 3

Razvoj leksikalnega analizatorja je precej preprost, če se uporablja teorija običajnih jezikov in končnih avtomatov. V okviru te teorije se razredi leksemov iste vrste obravnavajo kot formalni jeziki (jezik identifikatorjev, jezik konstant itd.), Katerih niz stavkov je opisan z ustrezno generativno slovnico. Poleg tega so ti jeziki tako preprosti, da jih ustvarja najpreprostejša slovnica - običajna slovnica.

Definicija 1. generativna slovnica G = , katerih pravila imajo obliko: A::=aB ali C::=b, kjer so A, B, C Є N; a, b Є Т se imenuje redno (samodejno).

Jezik L (G), ki ga generira avtomatska slovnica, se imenuje avtomatski (regularni) jezik ali jezik s končnim številom stanj.

Primer 1. Razred identifikatorjev, če je identifikator zaporedje, sestavljeno iz črk in številk in je prvi znak identifikatorja lahko le črka, opisuje naslednja generativna regularna slovnica G = , pri čemer

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

P = ( 1. I::= b

Tu sta b, c posplošena končna simbola za označevanje črk oziroma številk.

Postopek generiranja identifikatorja "bbcbc" je opisan z naslednjim zaporedjem zamenjav

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

Vendar glavna naloga LA ni generiranje leksikalnih enot, temveč njihovo prepoznavanje. Matematični model procesa prepoznavanja navadnega jezika je računalniška naprava, imenovana končni stroj (FA). Izraz "končni" poudarja, da ima računalniška naprava fiksno in končno količino pomnilnika ter obdeluje zaporedje vhodnih simbolov, ki pripadajo neki končni množici. Obstajajo različne vrste KA, če je izhodna funkcija KA (rezultat dela) samo pokazatelj ali je vhodno zaporedje simbolov sprejemljivo ali ne, se tak KA imenuje končni razreševalec.

Definicija 2. Naslednjih pet se imenuje končni avtomat:

A = , kjer je V = (a 1 , a 2 , …, a m ) – vhodna abeceda (končna množica simbolov);

Q = (q 0 , q 1 , …, q n -1 ) – abeceda stanj (končna množica simbolov);

δ: Q ×V →Q – prehodna funkcija;

q 0 Є Q – začetno stanje končnega avtomata;

F Є Q – množica končnih stanj.

Shema delovanja vesoljskega plovila.

Obstaja neskončen trak, razdeljen na celice, od katerih lahko vsaka vsebuje en simbol iz V. Na traku je zapisana veriga α Є V*. Celice levo in desno od verige so prazne. Obstaja končna krmilna naprava (FCU) z bralno glavo, ki lahko zaporedno bere znake s traku, ki se premikajo po traku od leve proti desni. V tem primeru je krmilna enota lahko v katerem koli stanju od Q. Krmilna enota vedno začne svoje delo v začetnem stanju q 0 in konča v enem od končnih stanj F. Vsakič se premakne v novo celico na trak, krmilna enota preide v novo stanje v skladu s funkcijo δ.

Prehodno funkcijo vesoljskega plovila lahko predstavimo na naslednje načine:

· Niz ekip;

· Diagram stanja;

· Prehodna miza.

Ukaz državnega stroja je zapisan takole:

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

Ta ukaz pomeni, da je avtomat stanja v stanju q i, prebere simbol a j s traku in preide v stanje q k.

Grafično je ukaz predstavljen kot lok grafa, ki poteka od točke q i do točke q k in je označen s simbolom a j vhodne abecede:

Grafična predstavitev celotne preslikave δ se imenuje diagram stanja končnega avtomata.

Če se vesoljsko plovilo znajde v situaciji (q i, a j), ki ni leva stran nobenega ukaza, se ustavi. Če krmilna enota prešteje vse simbole verige α, posnete na traku, in hkrati preide v končno stanje q r Є F, potem pravijo, da je veriga α dovoljena s končnim strojem.

Tabela prehodov vesoljskega plovila je sestavljena na naslednji način: stolpci matrike ustrezajo simbolom iz vhodne abecede, vrstice ustrezajo simbolom iz abecede stanja, elementi matrike pa ustrezajo stanjem, v katera preide vesoljsko plovilo za dano kombinacijo vhodnega simbola. in državni simbol.

Naj bo regularna slovnica G = , katerih pravila imajo obliko: A i::= a j A k ali A i::= a j, kjer so A i, A k Є N in a j Є T.

Potem je končni avtomat A = , ki dopušča isti jezik, kot ga generira običajna slovnica G, je sestavljen na naslednji način:

2) Q = N U (Z), Z N in Z T, Z je končno stanje vesoljskega plovila;

5) Preslikava δ je zgrajena v obliki:

· Vsako nadomestno pravilo v slovnici G oblike A i::= a j A k je povezano z ukazom (A i, a j) → A k;

· Vsako nadomestno pravilo oblike A i::= a j je povezano z ukazom (A i, a j) → Z;

Primer 2. Konstruirajte CA za slovnico iz primera 1. Imamo A = , Kje

1) V = T = (b, c)

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

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

5) δ: a) v obliki nabora ukazov:

b) v obliki diagrama stanja

Obstajajo deterministični in nedeterministični končni avtomati. Vesoljsko plovilo se imenuje nedeterministični KA (NKA), če v njenem diagramu stanja izhaja iz enega oglišča več lokov z enakimi oznakami. Na primer, KA iz primera 2 je NKA.

Za praktične namene je potrebno, da končni razpoznavalec sam določi trenutek konca vnosnega zaporedja znakov in izda sporočilo o pravilnosti ali napaki vnosnega zaporedja. Za te namene velja, da je vhodna veriga na desni omejena s končnim markerjem ├, interpretirana stanja pa se vnesejo v diagram stanja vesoljskega plovila:

Z – "dovoli vhodno verigo";

O – »v vhodni verigi je bila zapomnila napaka«;

E – "zavrni vhodno verigo."

Stanji Z in E sta končni in vesoljsko plovilo gre vanje, ko bere končni marker ├, po obdelavi pravilne ali napačne vhodne verige. Stanje O je vmesno, vesoljsko plovilo se premakne vanj iz katerega koli veljavnega stanja vesoljskega plovila, ko je zaznana napaka v vhodni verigi in ostane tam, dokler ne prispe končni marker ├, po katerem preide v stanje E - »zavrni vhodno verigo. ”

Naj sta L 1 in L 2 jezika v abecedi

Potem, tj. jezikovno veriženje sestoji iz združevanja vseh besed prvega jezika z vsemi besedami drugega jezika. Zlasti če , potem , in če , potem .

Uvedimo zapis za "stopnje" jezika L:

Tako L i vključuje vse besede, ki jih je mogoče razdeliti na i zaporednih besed iz L .

Iteracijo (L) * jezika L tvorijo vse besede, ki jih je mogoče razdeliti na več zaporednih besed iz L:

Lahko ga predstavimo s stopinjami:

Pogosto je priročno upoštevati "okrnjeno" ponovitev jezika, ki ne vsebuje prazne besede, če ta v jeziku ne obstaja: . To ni nova operacija, ampak preprosto priročna okrajšava za izraz.

Upoštevajte tudi, da če abecedo obravnavamo kot končni jezik, sestavljen iz besed z eno črko, potem prej uvedena notacija za množico vseh besed, vključno s praznimi besedami, v abecedi ustreza definiciji iteracije tega jezika.

Naslednja tabela ponuja formalno induktivno definicijo regularni izrazi nad abecedo in jeziki, ki jih predstavljajo.

Izraz r	Jezik L r
	L a =(a)
Naj sta r 1 in r 2	L r1 in L r2 -predstavljiva
regularni izrazi.	ti jeziki.
Nato naslednji izrazi
so redne	in predstavljajo jezike:
r=(r 1 +r 2)
r=(r 1 krog 2)
r=(r 1) *	L r =L r1 *

Pri snemanju regularni izrazi Izpustili bomo znak za veriženje in predvidevali, da ima operacija * višjo prioriteto kot veriženje in +, veriženje pa ima višjo prednost kot +. To bo omogočilo izpustitev številnih oklepajev. na primer lahko zapišemo kot 10(1 * + 0) .

Opredelitev 5.1. Dva regularni izrazi r in p naj bi bila enakovredna, če sta jezika, ki ju predstavljata, enaka, tj. L r = L p . V tem primeru pišemo r = p.

Preprosto je preveriti na primer naslednje lastnosti rednega operacije:

• r + p= p+ r (komutativnost unije),
• (r+p) +q = r + (p+q) (asociativnost zveze),
• (r p) q = r (p q) (asociativnost veriženja),
• (r *) * = r * (iteracijska idempotenca),
• (r +p) q = rq + pq(distributivnost).

Primer 5.1. Dokažimo kot primer ne tako očitno enakost: (r + p) * = (r * p *) *.

Naj bo L 1 jezik, ki ga predstavlja njegova leva stran, L 2 pa desna. Prazna beseda pripada obema jezikoma. Če je beseda neprazna, jo lahko po definiciji iteracije predstavimo kot veriženje podbesed, ki pripadajo jeziku. Toda ta jezik je podskupina jezika L"=L r * L p * (zakaj?). Zato . Nasprotno, če je beseda , potem jo je mogoče predstaviti kot veriženje podbesed, ki pripadajo jeziku L ". Vsako od takih podbesed v je mogoče predstaviti v obliki v= v 1 1 ... v k 1 v 1 2 ... v l 2, kjer je za vse i=1, ... , k podbeseda in za vse j=1, ... , l je podbeseda (možno je, da je k ali l enako 0). Toda to pomeni, da je w veriženje podbesed, od katerih vsaka pripada in torej .

Običajni jezik

V teoriji jezika navaden niz(ali, v navadnem jeziku) imenujemo formalni jezik, ki izpolnjuje naslednje lastnosti. Te preproste lastnosti so takšne, da je razred pravilnih množic primeren za preučevanje kot celoto, dobljeni rezultati pa so uporabni v številnih pomembnih primerih formalnih jezikov. To pomeni, da je koncept pravilne množice primer matematične strukture.

Definicija pravilne množice

Naj bo Σ končna abeceda. Redni komplet R(Σ) v abecedi Σ definirajo naslednje rekurzivne lastnosti:

Poglej tudi

• Gradnja razčlenjevalnika na osnovi pristopa avtomatov

Fundacija Wikimedia. 2010.

Oglejte si, kaj je "običajni jezik" v drugih slovarjih:

običajni jezik- - Telekomunikacijske teme, osnovni pojmi EN običajni jezik... Priročnik za tehnične prevajalce

- (latinsko regularius, iz regula pravilo). Pravilno, pravilno urejeno, narejeno. Redno delovanje stroja. Celo kap. Redno življenje. Korektno, spodobno, monotono življenje. Slovar tujih besed, vključenih v ruski jezik.... ... Slovar tujih besed ruskega jezika

cm … Slovar sinonimov

Starodavni pisni jezik- Jezik z dolgo pisno tradicijo, to je, da je pred več stoletji dobil pisavo, prilagojeno strukturi danega jezika, delovanje pisne različice jezika pa ni bilo epizodično, ampak redno, z... . .. Slovar sociolingvističnih izrazov

Ta izraz ima druge pomene, glej Quechua. Quechua Samoime: Qhichwa Simi, Runa Simi Države ... Wikipedia

Okvir stavbe z mrežo stebrov ali stebrov, ki temelji na stopnici enake velikosti (bolgarščina; Български) enoten skelet (češčina; čeština) pravidelný skelet (nemščina; nem.) regelmäßiges Skelett (madžarščina; madžarščina) szabályos... ... Gradbeni slovar

- [FRANCOSKI PARK] park, ki ima geometrično pravilen tloris, navadno osno tloris (bolgarsko; български) frenski park (češko; čeština) francouzský park (nemško; nem.) park regelmäßiger; Französischer Park…… Gradbeni slovar

Quechua Samoime: Qhichwa Simi, Runa Simi Države: Argentina, Bolivija, Kolumbija, Peru, Čile, Ekvador Regije: Andi Uradni status: Peru ... Wikipedia

Tagalog jezik- (tagal, tagala, tagalo; tagalog) eden od filipinskih jezikov. Območje začetne razširjenosti je v politično, gospodarsko in kulturno najbolj pomembni regiji Republike Filipinov - osrednjem in južnem delu otoka... ... Jezikoslovni enciklopedični slovar

knjige

• Izpeljani glagoli. Skrivnosti finske slovnice. Učbenik, Safronov V.D.. Priročnik je posvečen enemu najbolj zanimivih in nezadostno predstavljenih razdelkov finske slovnice v izobraževalni literaturi v ruskem jeziku - izpeljanim glagolom. Tvorijo se iz glagolov in iz imen...