Običajni jeziki in končni avtomati. Končni avtomati in običajni jeziki Teorija formalnih jezikov za lutke

Poznamo operacije združevanja jezikov. Definirajmo operaciji veriženja in iteracije (včasih imenovane Kleenejevo zapiranje).

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 oznaka za nabor vseh besed, vključno s praznimi besedami, v abecedi ustreza definiciji ponovitve tega jezika.

Naslednja tabela podaja 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.	njihovi 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 Za r in p pravimo, da sta 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:	Lastnina
1		Opis
2		Prazna množica je pravilna množica v abecedi Σ
3		Množica, ki jo sestavlja le en prazen niz, je pravilna množica v abecedi Σ
4		Množica, sestavljena iz katerega koli simbola abecede Σ, je pravilna množica v abecedi Σ
5		Če sta kateri koli dve množici regularni v abecedi Σ, potem je tudi njuna unija regularna množica v abecedi Σ
6		Če sta katerikoli dve množici regularni v abecedi Σ, potem je tudi množica, sestavljena iz vseh možnih kombinacij parov njunih elementov, regularna množica v abecedi Σ
		Če je katera koli množica regularna v abecedi Σ, potem je tudi množica vseh možnih kombinacij njenih elementov regularna množica v abecedi Σ

Nič drugega kot naslednje ni pravilna množica v abecedi Σ

• Glej tudi

Gradnja razčlenjevalnika na osnovi pristopa avtomatov

Fundacija Wikimedia.

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

- (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 pisni jezik, prilagojen 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; Deutsch) regelmäßiges Skelett (Madžarščina; Magyar) szabályos... ... Gradbeni slovar

- [FRANCOSKI PARK] park, ki ima geometrično pravilen tloris, navadno osno tloris (bolgarščina; Български) frenski park (češčina; čeština) francouzský park (nemščina; 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. je posvečen enemu najbolj zanimivih in premalo predstavljenih razdelkov finske slovnice v izobraževalni literaturi ruskega jezika - izpeljanim glagolom. Tvorijo se iz glagolov in iz imen...

Redne slovnice, končni avtomati in regularni nizi (ter regularni izrazi, ki jih predstavljajo) so trije različni načini določanja regularnih jezikov.

Izjava

Jezik je PM, če in samo če je določen z levo-linearno (desno-linearno) slovnico. Jezik je mogoče definirati z levo-linearno (desno-linearno) slovnico, če in samo če je pravilna množica.

Jezik je PM, če in samo če ga določa končni avtomat. Državni stroj prepozna jezik, če in samo če je PM.

Vse te tri metode so enakovredne. Obstajajo algoritmi, ki omogočajo, da se za jezik, definiran na enega od teh načinov, konstruira druga metoda, ki definira isti jezik. Podroben opis teh algoritmov je na voljo v literaturi (glej seznam).

Če želite na primer najti regularni izraz za jezik, ki ga definira desnolinearna slovnica, je treba sestaviti in rešiti sistem enačb z regularnimi koeficienti.

V teoriji programskih jezikov ima najpomembnejšo vlogo enakovrednost CA in običajnih slovnic, saj se s takimi slovnicami definirajo leksikalne strukture programskih jezikov. Ko ustvarimo avtomat, ki temelji na znani slovnici, dobimo razpoznavalec za dani jezik. Na ta način je mogoče rešiti problem razčlenjevanja leksikalnih konstrukcij jezika.

Če želite zgraditi CA na podlagi znane običajne slovnice, ga je treba zmanjšati na avtomatsko obliko. Množica stanj avtomata bo ustrezala množici neterminalnih simbolov slovnice. 2.3.2 Lastnosti navadnih jezikov

Množica se imenuje zaprta glede na neko operacijo, če kot rezultat izvajanja te operacije na katerem koli od njenih elementov dobimo nov element, ki pripada isti množici.

Pravilni nizi so zaprti pod operacijami preseka, združevanja, seštevanja, ponavljanja, veriženja, spreminjanja imen simbolov in zamenjave nizov za simbole.

Za običajne jezike je mogoče rešiti veliko težav, ki so nerešljive za druge vrste jezikov. Na primer, naslednje težave so rešljive ne glede na to, na kakšen način je naveden jezik:

Problem enakovrednosti: dana sta dva običajna jezika L 1 (V) in L 2 (V). Ugotoviti je treba, ali sta enakovredna.

Problem verižne pripadnosti jeziku. Podan je običajni jezik L(V), niz simbolov V * . Preveriti moramo, ali ta veriga pripada jeziku.

Problem praznine jezika. Glede na običajni jezik L(V). Treba je preveriti, ali je ta jezik prazen, tj. najti vsaj eno verigo, L(V).

Včasih je treba dokazati, ali je določen jezik reden. Če je ta jezik mogoče določiti na enega od obravnavanih načinov, potem je običajen. Če pa takšne metode ni mogoče najti, ni znano, ali jezik ni pravilen ali preprosto ni bilo mogoče najti načina, da bi ga določili. Obstaja preprosta metoda za preverjanje, ali je zadevni jezik pravilen. Dokazano je, da če je za določen jezik t.i razširitvena lema, potem je pravilna. Če ta lema ni izpolnjena, jezik ni pravilen.

Lema rasti je formulirana na naslednji način. Če je dan navaden jezik in dovolj dolga veriga simbolov, ki pripadajo temu jeziku, potem lahko v njem najdemo neprazen podniz, ki se lahko ponovi kolikorkrat želimo, in vse tako dobljene verige bodo prav tako pripadale običajni jezik v vprašanju.

Formalno je lema zapisana takole. Če je podan jezik L, potem je konstanta p>0 takšna, da če sta L in p, lahko verigo zapišemo v obliki, kjer je 0

Primer. Razmislite o jeziku L=(a n b n n>0). Dokažimo, da ni pravilno z uporabo leme o širjenju jezikov.

Naj bo ta jezik pravilen, potem mora zanj veljati lema o rasti. Vzemimo neko verigo tega jezika = a n b n in jo zapišimo v obliki. Če je a + ali b + , potem veriga i ne pripada jeziku za noben i, kar je v nasprotju s pogoji leme. Če je a + b + , tudi veriga 2 ne pripada jeziku L. Dobili smo protislovje, torej jezik ni regularen.

Redni kompletiin regularni izrazi

Redni kompleti

V tem razdelku bomo obravnavali razred nizov verig nad končnim slovarjem, ki jih je zelo enostavno opisati z nekakšnimi formulami. Ti nizi se imenujejo običajni.

Definicija 1.Naj V 1 in V 2 - veliko verig. Opredelimo tri operacijena teh sklopih.

Zveza: V 1 V 2 =(|   V 1 ) ali   V 2 .

Veženje (produkt, lepljenje): Vl V2 = (|  V 1 ,  V 2 ) Predznak operacije veriženja običajno izpustimo.

primer: V, = (abc, ba),V 2 = (b, cb). V1V2 =(abcb, abccb, bab, bacb).

Označimo z V n produkt n množic V:V n =VV...V,V° =() (tukaj je  prazna veriga).

primer: V 1 = (abc, ba), V 1 2 = (abcabc, abcba, baba, baabc).

3. Ponovitev: V* = V 0 V 1 V 2 ... =   =0 ∞ V n .

primer: V = (a, bc), V* = (, a, bc, aa, abc, bcbc, bca, aaa, aabc,...).

Opredelitev 4.13.Razred regularnih množic nad končnim slovarjem V opredelitigre takole:

zveza ST;

veriženje ST;

ponovitev S* in T*.

5. Če množice ni mogoče sestaviti s končno uporabo pravil 1-4, potem je neregularna.

Primeri pravilnih nizov: (ab, ba)* (aa); (b)((c)(d, ab)*). Primeri nepravilnih množic: (a n b n | n > 0); ( | v verigi  število pojavitev simbolov a in b sovpada).

Regularni izrazi

Regularne množice so dobre, ker jih je mogoče zelo preprosto opisati s formulami, ki jih bomo imenovali regularni izrazi.

Definicija 2.Razred regularnega izraza nad končnim slovarjem V opredelitigre takole:

njihova vsota R1+R2;

njihov produkt R1R2;

njihova ponovitev R1* in R2*.

4. Če izraz ni konstruiran s končno uporabo pravil 1-3, potem ni regularen.

Simbol dela lahko izpustite. Za zmanjšanje števila oklepajev, kot v kateri koli algebri, se uporabljajo prioritete operacij: iteracija ima najvišjo prednost; delo ima manjšo prednost; dodatek ima najnižjo prednost.

Primeri regularnih izrazov: ab + bа*; (aa)*b + (c + dab)*.

Očitno so si regularni nizi in regularni izrazi zelo blizu. Predstavljajo pa različne entitete: redna množica je množica verig (v splošnem primeru neskončna) in regularni izraz jeformula, ki shematično prikazuje, kako je bila ustrezna regularna množica sestavljena z uporabo zgoraj navedenih operacij(in ta formula je končna).

Naj bo R^ regularna množica, ki ustreza regularnemu izrazu R. Potem:

Tako je regularni izraz končna formula, ki definira neskončno število verig, torej jezik.

Oglejmo si primere regularnih izrazov in njihovih ustreznih jezikov.

Regularni izraz	Ustrezni jezik
	Vsi nizi, ki se začnejo z b, ki jim sledi poljubno število znakov a
	Vsi nizi a in b, ki vsebujejo natanko dve pojavitvi b
	Vse verige a in b, v katerih se simboli b pojavljajo samo v parih
(a+b)*(aa+bb)(a+b)*	Vse verige a in b, ki vsebujejo vsaj en par sosednjih a ali b
(0+1)*11001(0+1)*	Vse verige 0 in 1, ki vsebujejo podverigo 11001
	Vsi nizi a in b, ki se začnejo z a in končajo z b

Očitno je niz nizov pravilen, če in samo če ga je mogoče predstaviti z regularnim izrazom. Vendar pa je isti niz verig lahko predstavljen z različnimi regularnimi izrazi, na primer niz verig, ki je sestavljen iz simbolov a in vsebuje vsaj dva a, je lahko predstavljen z izrazi: aa*a; a*aaa*; aaa*; a*aa*aa* itd.

Definicija 3.Dva regularna izraza R1 in R2 se imenujejo enakovredni (označeni Rl = R2) takrat in samo takratR1 ^ = R2 ^ .

Tako je aa*a = a*aaa* = aaa* = a*aa*aa*. Postavlja se vprašanje, kako določiti enakovrednost dveh regularnih izrazov.

Izrek1 . Za vse regularne izraze R, S in T pošteno:

Te relacije lahko dokažemo s preverjanjem enakosti ustreznih nizov verig. Uporabljajo se lahko za poenostavitev regularnih izrazov. Na primer: b (b + aa*b) = b (b + aa*b) = b ( + aa*) b = ba*b. Zato b (b + aa*b) = ba*b, kar ni očitno.

Kleenejev izrek

Regularni izrazi so končne formule, ki definirajo regularne jezike. A tudi končni avtomati imajo podobno lastnost – definirajo tudi jezike. Postavlja se vprašanje: kako so razredi jezikov, ki jih definirajo končni avtomati in regularni izrazi, povezani drug z drugim? Označimo In veliko samodejnih jezikov, R je nabor običajnih jezikov. Stephen Kleene, ameriški matematik, je dokazal naslednji izrek.

Izrek2 . (Kleenejev izrek.) Razredi pravilnih množic in avtomatskih jezikov sovpadajo, tj. A = R .

Z drugimi besedami, vsak avtomatski jezik je mogoče podati s formulo (regularnim izrazom) in vsak regularni niz lahko prepozna končni avtomat. Ta izrek bomo konstruktivno dokazali v dveh korakih. Na prvem koraku bomo dokazali, da je vsak avtomatski jezik regularna množica (ali, kar je enako, za vsak končni avtomat lahko sestavimo regularni izraz, ki podaja jezik, ki ga ta avtomat prepozna). V drugem koraku dokažemo, da je vsaka regularna množica avtomatski jezik (ali, kar je enako, iz katerega koli regularnega izraza lahko sestavimo končni avtomat, ki dovoljuje natanko verige ustrezne regularne množice).

Predstavimo model prehodnega grafa kot posplošitev modela končnega avtomata. Prehodni graf ima eno začetno in poljubno število končnih vozlišč, usmerjeni robovi pa so za razliko od končnega avtomata označeni ne s simboli, temveč z regularnimi izrazi. Prehodni graf dopušča verigo a if A pripada nizu verig, opisanih s produktom regularnih izrazov R 1 R 2 ...R n , ki označujejo pot od začetne točke do enega od končnih točk. Nabor verig, ki jih dovoljuje prehodni graf, tvori jezik, ki ga dovoljuje.

riž. 1. Graf prehodov

Na sl. Slika 1 prikazuje prehodni graf, ki omogoča npr. verigo abbca, saj je pot s->r->p->s->r->q, ki vodi do končnega stanja q, označena z verigo regularni izrazi ab* c*a. Končni avtomat je poseben primer prehodnega grafa, zato so vsi jeziki, ki jih sprejemajo državni avtomati, podprti tudi s prehodnimi grafi.

Izrek 3.Vsak avtomatski jezik je reden niz, A  R.

Dokaz. Prehodni graf z enim začetnim in enim končnim ogliščem, v katerem je edini rob od začetnega do končnega oglišča označen z regularnim izrazom R, dopušča jezik R^ (slika 1).

riž. 2. Prehodni graf, ki dopušča običajni jezik FT

Dokažimo zdaj, da je vsak avtomatski jezik pravilna množica z redukcijo katerega koli prehodnega grafa, ne da bi spremenili jezik, ki ga omogoča, v enakovredno obliko (slika 2).

Vsak končni avtomat in katerikoli prehodni graf je vedno mogoče predstaviti v normalizirani obliki, v kateri obstaja samo eno začetno oglišče s samo izhodnimi robovi in ​​samo eno končno oglišče s samo vhodnimi robovi (slika 3).

riž. 3. Prehodni graf z enim začetnim in enim končnim vozliščem

S prehodnim grafom, predstavljenim v normalizirani obliki, je mogoče izvesti dve operaciji redukcije - redukcijo robov in redukcijo vozlišč - ob ohranjanju jezika, ki ga dovoljuje ta prehodni graf:

a) zmanjšanje reber:

B ) zmanjšanje vozlišča (zamenjava se izvede za vsako pot, ki poteka skozi točko p, čemur sledi zavrženje kot nedosegljivo stanje):

Očitno je, da vsaka operacija redukcije ne spremeni jezika, ki ga prepozna prehodni graf, ampak zmanjša bodisi število robov ali število vozlišč, na koncu pa redukcije pripeljejo prehodni graf v obliko, prikazano na sliki. 2. Izrek je dokazan: vsak avtomatski jezik je regularna množica.

Primer

Naj bo podan končni stroj A:

Konstruiramo enakovredni prehodni graf v normalizirani obliki.

Zmanjšanje vrha 3:

Redukcija lokov in uporaba pravila R = R:

Zmanjšanje vrha 2:

Redukcija loka in oglišča 1:

Tako je jezik, ki ga prepozna avtomat A, podan z regularnim izrazom: R A = b+(a+bb)(b+ab)*a.

Dokažimo Kleenejev izrek v drugo smer.

2. izrek.Vsak običajni niz je avtomatski jezik: R A.

Dokaz. Pokažimo, da je za vsak regularni izraz R mogoče konstruirati končni avtomat A r (po možnosti nedeterminističen), ki prepozna jezik, določen z R. Take avtomate bomo definirali rekurzivno.

(začetno in končno stanje A sta združena).

Primer(nadaljevanje)