Uobičajeni jezik. Metode definiranja regularnih jezika Teorija formalnih jezika za lutke

U ovom poglavlju počinjemo predstavljati elemente teorije formalnih jezika.

Kada kažemo "formalni jezik", mislimo na to da se ovdje predstavljeni rezultati prvenstveno koriste u opisivanju umjetnih jezika koje su izmislili ljudi za posebne svrhe, kao što su programski jezici. Ali ne postoji nepremostiva prepreka između posebno izmišljenih umjetnih (formalnih) jezika i prirodnih jezika koji spontano nastaju i razvijaju se. Ispada da prirodne jezike karakteriziraju složena gramatička pravila, tj. su prilično rigidno formalizirani, a čak i "znanstveno najrazvijeniji" programski jezik sadrži "tamna mjesta", čije nedvosmisleno razumijevanje predstavlja problem.

Tri su glavna aspekta koja morate imati na umu kada učite jezike.

Prvi je jezična sintaksa . Jezik je neka vrsta skupa "riječi", gdje je "riječ" određeni konačni niz "slova" - simbola neke unaprijed utvrđene abecede. Pojmovi "slovo" i "riječ" mogu se razumjeti na različite načine (matematička definicija ovih pojmova bit će dana u nastavku). Dakle, "slova" zapravo mogu biti slova abecede nekog prirodnog ili formalnog jezika, na primjer, ruskog jezika ili programskog jezika Pascal. Tada će "riječi" biti konačni nizovi "slova": krokodil, " cijeli broj". Takve se riječi nazivaju "leksemima". Ali "slovo" može biti "riječ" ("leksem") kao cjelina. Tada su "riječi" rečenice prirodnog jezika ili programa programskog jezika. Ako neki skup "slova" fiksna, onda neće svaki njihov niz biti "riječ", tj. "Eleksem" određenog jezika, već samo niz koji poštuje određena pravila. Riječ "krykadil" nije leksem u ruskom, a riječ "iff" nije leksem u Pascalu. Rečenica "Volim te" nije ispravna rečenica na ruskom jeziku, baš kao što zapis "x:= =t" nije ispravno napisan Pascal operator dodjele. Sintaksa* jezika je sustav pravila u skladu s kojima se mogu konstruirati "ispravni" nizovi "slova". Svaku riječ nekog jezika karakterizira određena struktura specifična za taj određeni jezik. Tada je potrebno, s jedne strane, razviti mehanizme za nabrajanje, odnosno generiranje riječi sa zadanom strukturom, as druge strane, mehanizme za provjeru pripadnosti date riječi određenom jeziku. Prije svega, upravo te mehanizme proučava klasična teorija formalnih jezika.

Drugi aspekt - semantika jezika . Semantika** uključuje povezivanje riječi jezika s određenim "značenjem", Značenjem." Na primjer, kada pišemo matematičku formulu, moramo slijediti određena sintaktička pravila (stavljanje zagrada, pravopis simbola, redoslijed simbola itd.). ), ali, osim toga, formula ima vrlo određeno značenje, znači nešto.

Jezik je sredstvo komunikacije i prijenosa informacija. Ako želimo da budemo shvaćeni, moramo ne samo sintaktički ispravno graditi svoj govor, pazeći na pravilan redoslijed slova u riječi i riječi u rečenici, nego moramo voditi računa o njegovom značenju, o idejama koje izražavamo u govoru. Matematičke teorije "značenja" pojavile su se relativno nedavno, a uz sljedeće poglavlje vrlo kratko ćemo se osvrnuti na neke pristupe matematičkom opisu semantike programskih jezika.

* Riječ "sintaksa" dolazi od starogrčkog "syn" - "zajedno" i "taxis" - "red, struktura". Dakle, sintaksa se može shvatiti kao "kompozicija".

** Od starogrčkih riječi "sema" - "znak, predznak" i "semanticos" - "označavanje".

Konačno, treći aspekt - pragmatika jezika . Pragmatika je povezana s ciljevima koje si izvorni govornik postavlja: na primjer, osoba izgovara govor s ciljevima koji se ne odnose na sintaksu, ne na semantiku jezika na kojem govori ili piše, već, recimo, na primanje određeni iznos novca za svoj govor.iznosi novca. Pragmatika je prije socio-filozofska disciplina koja utječe na aktivnost postavljanja ciljeva pojedinca. Nećemo ga ni najmanje dirati.

U ovom će se poglavlju prvo ispitati temeljni koncepti matematičke teorije formalnih jezika, među kojima je najvažniji koncept generativne gramatike, a potom i tzv. regularni jezici. Teorija regularnih jezika, zajedno s teorijom konačnih automata, čini temelj cjelokupne teorije formalnih jezika.

• Abeceda, riječ, jezik

• Generativne gramatike

  Kao što je već navedeno, klasična teorija formalnih jezika prvenstveno proučava sintaksu jezika. Uvodi matematički model sintakse koji opisuje mehanizme za generiranje i prepoznavanje "dobro oblikovanih" lanaca. U ovom dijelu ćemo pogledati prvi od ovih mehanizama.

Poznajemo operacije kombiniranja jezika. Definirajmo operacije ulančavanja i iteracije (ponekad zvane Kleene zatvaranje).

Neka su L1 i L2 jezici u abecedi

Zatim, tj. ulančavanje jezika sastoji se od ulančavanja svih riječi prvog jezika sa svim riječima drugog jezika. Konkretno, if , then , and if , then .

Uvedimo notaciju za “stupnjeve” jezika L:

Dakle, L i uključuje sve riječi koje se mogu podijeliti na i uzastopnih riječi iz L .

Iteraciju (L) * jezika L tvore sve riječi koje se mogu podijeliti u nekoliko uzastopnih riječi iz L:

Može se predstaviti pomoću stupnjeva:

Često je zgodno razmotriti "skraćenu" iteraciju jezika, koja ne sadrži praznu riječ ako ona ne postoji u jeziku: . Ovo nije nova operacija, već jednostavno zgodna skraćenica za izraz .

Napomenimo također da ako abecedu smatramo konačnim jezikom koji se sastoji od jednoslovnih riječi, tada prethodno uvedena oznaka za skup svih riječi, uključujući praznu, u abecedi odgovara definiciji iteracije ovog jezika.

Sljedeća tablica daje formalnu induktivnu definiciju regularni izrazi nad abecedom i jezicima koje predstavljaju.

Izraz r	Jezik L r
	L a = (a)
Neka su r 1 i r 2	L r1 i L r2 -predstavljivi
regularni izrazi.	njima jezicima.
Zatim slijede sljedeći izrazi
su redoviti	i predstavljaju jezike:
r=(r 1 +r 2)
r=(r 1 krug 2)
r=(r 1) *	L r =L r1 *

Prilikom snimanja regularni izrazi Izostavit ćemo znak ulančavanja i pretpostaviti da operacija * ima veći prioritet od ulančavanja i +, a ulančavanje ima veći prioritet od +. Ovo će omogućiti izostavljanje mnogih zagrada. Na primjer, može se napisati kao 10(1 * + 0) .

Definicija 5.1. Dva regularni izrazi Za r i p se kaže da su ekvivalentni ako su jezici koje predstavljaju isti, tj. L r = L p . U ovom slučaju pišemo r = p.

Lako je provjeriti npr. sljedeće svojstva regularnih operacije:

• r + p= p+ r (komutativnost unije),
• (r+p) +q = r + (p+q) (asocijativnost unije),
• (r p) q = r (p q) (asocijativnost ulančavanja),
• (r *) * = r * (iteracijska idempotencija),
• (r +p) q = rq + pq(distributivnost).

Primjer 5.1. Dokažimo, kao primjer, ne tako očitu jednakost: (r + p) * = (r * p *) *.

Neka je L1 jezik predstavljen lijevom stranom, a L2 desnom stranom. Prazna riječ pripada obama jezicima. Ako je riječ neprazna, tada se prema definiciji iteracije može prikazati kao ulančavanje podriječi koje pripadaju jeziku. Ali ovaj jezik je podskup jezika L"=L r * L p * (zašto?). Stoga . Obrnuto, ako je riječ , tada ju je moguće predstaviti kao ulančavanje podriječi koje pripadaju jeziku L". Svaka od takvih podriječi v može se predstaviti u obliku v= v 1 1 ... v k 1 v 1 2 ... v l 2, gdje je za sve i=1, ... , k podriječ i za sve j=1, ... , l je podriječ (moguće je da je k ili l jednako 0). Ali to znači da je w spoj podriječi, od kojih svaka pripada i, prema tome, .

Teorija automata - ovo je dio teorije sustavi upravljanja, proučavajući matematičke modele diskretnih pretvarača informacija, tzv strojnice. S određene točke gledišta, takvi pretvarači su i stvarni uređaji (računala, automati, živi organizmi itd.) i apstraktni sustavi (na primjer, formalni sustav, aksiomatske teorije itd.), što omogućuje primjenu teorije automata u raznim znanstvenim i primijenjenim istraživanjima. Teorija automata najuže je povezana s matematičkom logikom i teorijom algoritama. Konkretno, pomoću teorije automata dokazuje se rješivost nekih formalnih računa.

Još jedan važan predmet proučavanja ovog kolegija je formalni jezik 1 – proizvoljan skup riječi neke abecede. Važnost formalnih jezika za teorijsku informatičku znanost je zbog činjenice da je najjednostavniji i najprikladniji model podataka koji se koristi u računalnim programima konačni niz, čiji je svaki element preuzet iz nekog unaprijed fiksnog konačnog skupa. Budući da su formalni jezici koji se koriste u aplikacijama obično beskonačni, potreban je način da se formalni jezik opiše na konačan način. U ovom tečaju proučavat ćemo 3 klasična načina ovog opisa: strojnice, regularni izrazi I generativne gramatike.

Uvod

1. Osnovni pojmovi teorije formalnih jezika

Promotrimo neprazan konačni skup A, koji se sastoji od znakova ( a 1 , …, a k). Nazvat ćemo A abeceda , a njegovi simboli su slova . Bilo koji konačni niz slova ove abecede naziva se u jednoj riječi (lanac ili crta ): w=a 1 a 2 …a n- riječ ( a ja A), |w| – duljina riječi (broj slova koja čine riječ, pri čemu se svaki znak pojavljuje onoliko puta koliko se pojavljuje u w). Preko | w| b označavaju broj pojavljivanja simbola b po riječi w.

Beskonačan niz slova abecede A nazvao nadriječ , - nadriječ od beskonačnog broja slova A. Prazan je riječ koja ne sadrži niti jedno slovo. Označava se sa . Očito ||=0.

- mnoge riječi abecede A duljina n. Skup svih riječi abecede A(uključujući superriječi). A*. Ovaj skup je prebrojiv jer je unija prebrojivog broja konačnih skupova
. Skup svih nepraznih riječi u abecedi A označen sa A+ . Ako A={a), To A*={a)* bit će označen sa A*.

Bilo koji podskup
nazvao jezik (formalni jezik ) iznad abecede A.

Ako x I g– riječi jezika
, zatim riječ xy(rezultat pripisivanja riječi na na kraju riječi x) Zove se ulančavanje (kvačilo , raditi ) riječi x I na.
(n uzmimo već jednom x). Stavimo
.

Kažu da riječ x – podriječ riječi na, Ako g=uxv za neke riječi u I v. Sve podriječi riječi u jeziku
oblik mnogo podriječi Jezik L, što je označeno sa Subw( L).

Primjeri. 1. ba 3 =baaa,
- ova riječ ima podriječi ab, aba, ba i tako dalje.

2. Postavite ( a, abb) - jezik (konačni) preko abecede ( a, b}.

3. Puno
je jezik iznad abecede ( a, b). Ovaj jezik je beskrajan, sadrži riječi b, ba, aba, baa, abaa, baaa, aabaa, abaaa itd.

Budući da je svaki jezik skup, možemo razmotriti operacije unije, presjeka i razlike jezika definiranih preko iste abecede. Da, jezik
, Gdje
, nazvan komplementom jezika L u vezi s abecedom A. A ako je  uvijek uključeno u A*, zatim jezik
može ali ne mora sadržavati . U potonjem slučaju
.

Neka ,
. Tada se zove jezik ulančavanje (kvačilo , raditi ) Jezici I . pri čemu
,
(n puta) ako n>0.

Primjeri. 1. Ako
,
,To .

2. Ako je L=(0, 01), tada
.

Ponavljanje Jezik L zvan jezik
(ova se operacija također naziva Kleene zvjezdica ). Jezik
nazvao pozitivna iteracija Jezik L.

Primjer. Ako A={a, b) I L={aa, ab, ba, bb), To
.

Žalbom ili u zrcalnoj slici riječi w riječ se zove w R, u kojem su slova riječi w idite obrnutim redom. Na primjer, ako w=bac, To

Neka
. Zatim jezik
nazvao apel Jezik L.

Nazvat ćemo svaki početak riječi prefiks , i svaki kraj riječi - sufiks . Na primjer, ako g=xv, To x– prefiks riječi na(oznaka – x[g), A v– nastavak riječi na(oznaka – v]g). Očito, prazna riječ je i prefiks i sufiks bilo koje riječi. Svi prefiksi riječi u jeziku
oblik mnogo prefiksa ovog jezika: Pref( L)
. Slično Suf( L)
-m nož sufiksa Jezik
.

Ako jezik L je li to nikakva riječ L nije prefiks (sufiks) bilo koje druge riječi L, onda to kažu L ima prefiks (sufiks) vlasništvo .

Neka A 1 i A 2 – abecede. Ako prikaz f:
zadovoljava uvjet za sve riječi
I
, zatim preslikavanje f nazvao homomorfizam .

Bilješke. 1. Može se dokazati da ako f je onda homomorfizam
.

2. Homomorfizmi nisu uvijek bijekcije, ali svaki homomorfizam je jedinstveno određen svojim značenjem na riječi od jednog slova.

3. Primjena homomorfizma na jezik L, dobivamo drugi jezik f(L).

Ako f:
– homomorfizam,
I
, zatim kroz f(L 1) naveden je jezik
, i kroz
jezik je naznačen
, i sam zaslon
nazvao inverzija homomorfizma .

Primjeri. 1. Recimo da želimo svako pojavljivanje znaka 0 u nizu zamijeniti znakom A, a svako pojavljivanje 1 je uključeno bb. Tada možemo definirati homomorfizam f Tako
I
. Ako
, To
.

2. Neka f je homomorfizam za koji
I
. Zatim
I
.

Laboratorijski rad br.3

Razvoj leksičkog analizatora prilično je jednostavan ako se koristi teorija regularnih jezika i konačnih automata. U okviru ove teorije, klase leksema istog tipa smatraju se formalnim jezicima (jezik identifikatora, jezik konstanti, itd.), čiji je skup rečenica opisan pomoću odgovarajuće generativne gramatike. Štoviše, ovi jezici su toliko jednostavni da ih generira najjednostavnija gramatika - regularna gramatika.

Definicija 1. generativna gramatika G = , čija pravila imaju oblik: A::=aB ili C::=b, gdje su A, B, C Ê N; a, b Ê T nazivamo pravilnim (automatskim).

Jezik L (G) generiran automatskom gramatikom naziva se automatski (regularni) jezik ili jezik s konačnim brojem stanja.

Primjer 1. Klasa identifikatora, ako je identifikator niz koji se sastoji od slova i brojeva, a prvi znak identifikatora može biti samo slovo, opisuje se sljedećom generativnom regularnom gramatikom G = , pri čemu

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

P = ( 1. I::= b

Ovdje su b, c generalizirani terminalni simboli za označavanje slova odnosno brojeva.

Proces generiranja identifikatora "bbcbc" opisan je sljedećim nizom zamjena

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

Međutim, glavna zadaća LA nije generiranje leksičkih jedinica, već njihovo prepoznavanje. Matematički model procesa prepoznavanja regularnog jezika je računalni uređaj koji se naziva konačni stroj (FA). Izraz "konačan" naglašava da računalni uređaj ima fiksnu i konačnu količinu memorije i obrađuje niz ulaznih simbola koji pripadaju nekom konačnom skupu. Postoje razne vrste KA, ako je izlazna funkcija KA (rezultat rada) samo pokazatelj je li ulazni niz simbola prihvatljiv ili ne, takav KA se naziva konačni razrješivač.

Definicija 2. Sljedećih pet naziva se konačnim automatom:

A = , gdje je V = (a 1 , a 2 , …, a m ) – ulazna abeceda (konačan skup simbola);

Q = (q 0 , q 1 , …, q n -1 ) – abeceda stanja (konačan skup simbola);

δ: Q ×V →Q – prijelazna funkcija;

q 0 Ê Q – početno stanje konačnog automata;

F Ê Q – skup konačnih stanja.

Shema rada svemirske letjelice.

Postoji beskonačna traka, podijeljena na ćelije, od kojih svaka može sadržavati jedan simbol iz V. Lanac α Ê V* je napisan na traci. Ćelije lijevo i desno od lanca su prazne. Postoji uređaj za završnu kontrolu (FCU) s glavom za čitanje, koja može sekvencijalno čitati znakove s vrpce, krećući se po vrpci s lijeva na desno. U tom slučaju upravljačka jedinica može biti u bilo kojem stanju od Q. Kontrolna jedinica uvijek počinje svoj rad u početnom stanju q 0, a završava u jednom od završnih stanja F. Svaki put, prelazeći na novu ćeliju na trake, upravljačka jedinica prelazi u novo stanje u skladu s funkcijom δ.

Prijelazna funkcija svemirske letjelice može se prikazati na sljedeće načine:

· Skup timova;

· Dijagram stanja;

· Prijelazna tablica.

Naredba stroja stanja je napisana na sljedeći način:

(q i, a j) → q k, gdje su q i, q k Ê Q; a j Ê V.

Ova naredba znači da je automat stanja u stanju q i, čita simbol a j s trake i prelazi u stanje q k.

Grafički se naredba prikazuje kao luk grafa koji ide od vrha q i do vrha q k i označen je simbolom a j ulazne abecede:

Grafički prikaz cjelokupnog preslikavanja δ naziva se dijagram stanja konačnog automata.

Ako se letjelica nađe u situaciji (q i, a j), koja nije lijeva strana nijedne naredbe, tada se zaustavlja. Ako kontrolna jedinica prebroji sve simbole lanca α snimljene na vrpci, a istovremeno ide u konačno stanje q r Ê F, tada kažu da je lanac α dopušten od strane konačnog automata.

Prijelazna tablica svemirske letjelice konstruirana je na sljedeći način: stupci matrice odgovaraju simbolima iz ulazne abecede, redovi odgovaraju simbolima iz abecede stanja, a elementi matrice odgovaraju stanjima u koja letjelica ide za zadanu kombinaciju ulaznog simbola. i državni simbol.

Neka je regularna gramatika G = , čija pravila imaju oblik: A i::= a j A k ili A i::= a j, gdje su A i, A k Ê N i a j Ê T.

Tada je konačni automat A = , dopuštajući isti jezik koji generira regularna gramatika G, konstruira se na sljedeći način:

2) Q = N U (Z), Z N i Z T, Z je konačno stanje letjelice;

5) Preslikavanje δ je konstruirano u obliku:

· Svako supstitucijsko pravilo u gramatici G oblika A i::= a j A k pridružuje se naredbi (A i, a j) → A k;

· Svako pravilo zamjene oblika A i::= a j pridružuje se naredbi (A i, a j) → Z;

Primjer 2. Konstruirajte CA za gramatiku iz primjera 1. Imamo A = , Gdje

1) V = T = (b, c)

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

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

5) δ: a) u obliku skupa naredbi:

b) u obliku dijagrama stanja

Postoje deterministički i nedeterministički konačni automati. Svemirska letjelica se zove nedeterministički KA (NKA), ako u njegovom dijagramu stanja iz jednog vrha izlazi više lukova s ​​identičnim oznakama. Na primjer, KA iz primjera 2 je NKA.

U praktične svrhe potrebno je da završni prepoznavač sam odredi trenutak završetka unosa niza znakova i izda poruku o ispravnosti ili pogrešci unosa niza. U ove svrhe, ulazni lanac se smatra ograničenim s desne strane krajnjim markerom ├, a interpretirana stanja se unose u dijagram stanja svemirske letjelice:

Z – “dopusti lanac unosa”;

O – „zapamćena je pogreška u lancu unosa”;

E – "odbaci lanac unosa."

Stanja Z i E su konačna, a svemirska letjelica ide u njih kada očitava oznaku kraja ├, odnosno nakon obrade ispravnog ili pogrešnog lanca unosa. Stanje O je srednje, letjelica prelazi u njega iz bilo kojeg važećeg stanja letjelice kada se detektira pogreška u ulaznom lancu i ostaje tamo dok ne stigne krajnji marker ├, nakon čega prelazi u stanje E - „odbaci ulazni lanac. ”