Cunoaștem operațiunile de combinare a limbilor. Să definim operațiile de concatenare și iterare (uneori numite închidere Kleene).

Fie L 1 și L 2 limbi în alfabet

Apoi, adică concatenarea limbajului constă din concatenări ale tuturor cuvintelor din prima limbă cu toate cuvintele din a doua limbă. În special, dacă , atunci , și dacă , atunci .

Să introducem notația pentru „gradele” limbajului L:

Astfel, L i include toate cuvintele care pot fi împărțite în i cuvinte consecutive din L .

Iterația (L) * a limbii L este formată din toate cuvintele care pot fi împărțite în mai multe cuvinte consecutive din L:

Poate fi reprezentat folosind grade:

Este adesea convenabil să se ia în considerare o iterație „trunchiată” a limbii, care nu conține cuvântul gol dacă nu există în limbă: . Aceasta nu este o operațiune nouă, ci pur și simplu o prescurtare convenabilă pentru expresia .

De asemenea, rețineți că, dacă considerăm alfabetul ca un limbaj finit format din cuvinte cu o singură literă, atunci notația introdusă anterior pentru setul tuturor cuvintelor, inclusiv cuvintele goale, în alfabet corespunde definiției iterației acestui limbaj.

Următorul tabel oferă o definiție inductivă formală expresii obisnuite peste alfabet și limbile pe care le reprezintă.

Expresia r	Limba L r
	L a =(a)
Fie r 1 și r 2	L r1 si L r2 -reprezentabile
expresii obisnuite.	acestea limbi.
Apoi următoarele expresii
sunt regulate	și reprezintă limbile:
r=(r 1 +r 2)
r=(r 1 circr 2)
r=(r 1) *	L r =L r1 *

La înregistrare expresii obisnuite Vom omite semnul de concatenare și vom presupune că operația * are prioritate mai mare decât concatenarea și + , iar concatenarea are prioritate mai mare decât + . Acest lucru va permite omiterea multor paranteze. De exemplu, poate fi scris ca 10(1 * + 0) .

Definiție 5.1. Două expresii obisnuite r și p se spune că sunt echivalente dacă limbile pe care le reprezintă sunt aceleași, adică. L r = L p . În acest caz scriem r = p.

Este ușor să verificați, de exemplu, următoarele proprietățile regulate operatii:

• r + p= p+ r (comutativitatea uniunii),
• (r+p) +q = r + (p+q) (asociativitatea uniunii),
• (r p) q = r (p q) (asociativitatea concatenării),
• (r *) * = r * (idempotenta iterației),
• (r +p) q = rq + pq(distributivitatea).

Exemplul 5.1. Să demonstrăm, ca exemplu, o egalitate nu atât de evidentă: (r + p) * = (r * p *) *.

Fie L 1 limba reprezentată de partea sa stângă și L 2 de dreapta. Cuvântul gol aparține ambelor limbi. Dacă cuvântul este nevid, atunci prin definiția iterației poate fi reprezentat ca o concatenare a subcuvintelor aparținând limbii. Dar acest limbaj este un submult al limbajului L"=L r * L p * (de ce?). Prin urmare . În schimb, dacă un cuvânt , atunci este reprezentabil ca o concatenare a subcuvintelor aparținând limbajului L ". Fiecare dintre astfel de subcuvinte v este reprezentabil sub forma v= v 1 1 ... v k 1 v 1 2 ... v l 2, unde pentru toate i=1, ... , k este un subcuvânt și pentru toate j=1, ... , l este un subcuvânt (este posibil ca k sau l să fie egal cu 0). Dar aceasta înseamnă că w este o concatenare de subcuvinte, fiecare dintre ele aparținând și, prin urmare, .

Seturi obișnuiteși expresii regulate

Seturi obișnuite

În această secțiune vom lua în considerare o clasă de seturi de lanțuri peste un dicționar finit, care sunt foarte ușor de descris prin formule de un fel. Aceste seturi se numesc regulate.

Definiția 1.Lăsa V 1 Și V 2 - multe lanțuri. Să definim trei operațiipe aceste seturi.

Unirea: V 1 V 2 =(|   V 1 ) sau   V 2 .

Concatenare (produs, lipire): Vl V2 = (|  V 1 ,  V 2 ) Semnul operaţiei de concatenare este de obicei omis.

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

Să notăm cu V n produsul dintre n seturi V:V n =VV...V,V° =() (aici  este un lanț gol).

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

3. Iterație: V* = V 0 V 1 V 2 ... =   =0 ∞ V n .

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

Definiția 4.13.Clasă de mulțimi regulate peste un dicționar finit V definimerge asa:

unirea ST;

concatenare ST;

iterația S* și T*.

5. Dacă o mulțime nu poate fi construită printr-un număr finit de aplicații ale regulilor 1-4, atunci este neregulată.

Exemple de seturi regulate: (ab, ba)* (aa); (b)((c)(d, ab)*). Exemple de mulțimi neregulate: (a n b n | n > 0); ( | în lanț  numărul de apariții ale simbolurilor a și b coincide).

Expresii obisnuite

Seturile regulate sunt bune deoarece pot fi descrise foarte simplu prin formule, pe care le vom numi expresii regulate.

Definiția 2.Clasa de expresii regulate peste dicționar finit V definimerge asa:

suma lor R1+R2;

produsul lor R1R2;

iterația lor R1* și R2*.

4. Dacă o expresie nu este construită prin aplicarea finită a regulilor 1-3, atunci nu este regulată.

Simbolul de lucru poate fi omis. Pentru a reduce numărul de paranteze, ca în orice algebră, se folosesc prioritățile de operație: iterația are cea mai mare prioritate; lucrarea are mai puțină prioritate; adăugarea are cea mai mică prioritate.

Exemple de expresii regulate: ab + bа*; (aa)*b + (c + dab)*.

Evident, seturile regulate și expresiile regulate sunt foarte apropiate. Dar ele reprezintă entități diferite: o mulțime obișnuită este un set de lanțuri (în cazul general infinit) și expresia regulată esteo formulă care arată schematic modul în care a fost construit mulțimea obișnuită corespunzătoare folosind operațiile enumerate mai sus(și această formulă este finită).

Fie R^ o mulțime regulată corespunzătoare expresiei regulate R. Atunci:

Astfel, o expresie regulată este o formulă finită care definește un număr infinit de lanțuri, adică un limbaj.

Să ne uităm la exemple de expresii regulate și limbajele corespunzătoare.

Expresie uzuala	Limbajul corespunzător
	Toate șirurile care încep cu b urmate de un număr arbitrar de caractere a
	Toate șirurile lui a și b care conțin exact două apariții ale lui b
	Toate lanțurile lui a și b în care simbolurile b apar numai în perechi
(a+b)*(aa+bb)(a+b)*	Toate lanțurile a și b care conțin cel puțin o pereche de a sau b adiacente
(0+1)*11001(0+1)*	Toate lanțurile 0 și 1 care conțin sublanțul 11001
	Toate șirurile lui a și b, începând cu a și terminând cu b

Evident, un set de șiruri de caractere este regulat dacă și numai dacă poate fi reprezentat printr-o expresie regulată. Totuși, același set de lanțuri poate fi reprezentat prin expresii regulate diferite, de exemplu, un set de lanțuri format din simboluri a și care conține cel puțin două a poate fi reprezentat prin expresiile: aa*a; aaaa*; aaa*; a*aa*aa* etc.

Definiția 3.Două expresii regulate R1 Și R2 sunt numite echivalente (notate Rl = R2) atunci și numai cândR1 ^ = R2 ^ .

Astfel, aa*a = a*aaa* = aaa* = a*aa*aa*. Se pune întrebarea cum se determină echivalența a două expresii regulate.

Teorema1 . Pentru orice expresii regulate R, S Și T echitabil:

Aceste relații pot fi dovedite prin verificarea egalității sețiilor corespunzătoare de lanțuri. Ele pot fi folosite pentru a simplifica expresiile regulate. De exemplu: b (b + aa*b) = b (b + aa*b) = b ( + aa*) b = ba*b. Prin urmare, b (b + aa*b) = ba*b, ceea ce nu este evident.

teorema lui Kleene

Expresiile regulate sunt formulele finale care definesc limbajele regulate. Dar și mașinile cu stări finite au o proprietate similară - ele definesc și limbaje. Se pune întrebarea: cum se raportează între ele clasele de limbaje definite de mașinile cu stări finite și expresiile regulate? Să notăm Și multe limbi automate, R este un set de limbaje obișnuite. Stephen Kleene, un matematician american, a demonstrat următoarea teoremă.

Teorema2 . (Teorema lui Kleene.) Clasele de mulțimi regulate și limbaje automate coincid, adică A = R .

Cu alte cuvinte, fiecare limbaj automat poate fi specificat printr-o formulă (expresie regulată) și fiecare set regulat poate fi recunoscut de un automat finit. Vom demonstra această teoremă constructiv, în doi pași. În primul pas, vom demonstra că orice limbaj automat este o mulțime regulată (sau, ceea ce este la fel, pentru orice automat finit putem construi o expresie regulată care specifică limbajul recunoscut de acest automat). În a doua etapă, vom demonstra că orice mulțime regulată este un limbaj automat (sau, ceea ce este la fel, din orice expresie regulată se poate construi un automat finit care admite exact lanțurile mulțimii regulate corespunzătoare).

Să introducem modelul grafului de tranziție ca o generalizare a modelului automat finit. Graficul de tranziție are o inițială și un număr arbitrar de vârfuri finale, iar muchiile direcționate sunt marcate, spre deosebire de un automat finit, nu cu simboluri, ci cu expresii regulate. Graficul de tranziție admite un lanț a if A aparține unui set de lanțuri, descrise prin produsul expresiilor regulate R 1 R 2 ...R n , care marchează drumul de la vârful inițial la unul dintre vârfurile finale. Setul de lanțuri permise de graficul de tranziție formează limbajul permis de acesta.

Orez. 1. Graficul de tranziție

În fig. Figura 1 prezintă un grafic de tranziție care permite, de exemplu, un lanț abbca, întrucât calea s->r->p->s->r->q, care duce la starea finală q, este marcată cu un lanț de expresii regulate  a b*   c*a. O mașină cu stări finite este un caz special al unui grafic de tranziție și, prin urmare, toate limbajele care sunt acceptate de mașinile cu stări sunt, de asemenea, suportate de graficele de tranziție.

Teorema 3.Fiecare limbaj automat este un set obișnuit, A  R.

Dovada. Un grafic de tranziție cu un vârf inițial și unul final, în care singura muchie de la vârful inițial la cel final este etichetată cu o expresie regulată R, admite limbajul R^ (Fig. 1).

Orez. 2. Graficul de tranziție care admite limbajul obișnuit FT

Să demonstrăm acum că fiecare limbaj automat este o mulțime obișnuită prin reducerea oricărui graf de tranziție fără a schimba limbajul pe care îl permite la o formă echivalentă (Fig. 2).

Orice automat finit și orice graf de tranziție poate fi întotdeauna reprezentat într-o formă normalizată, în care există un singur vârf inițial cu doar muchii de ieșire și un singur vârf final cu doar muchii de intrare (Fig. 3).

Orez. 3. Graficul de tranziție cu un vârf inițial și unul final

Cu un grafic de tranziție prezentat într-o formă normalizată, pot fi efectuate două operații de reducere - reducerea marginilor și reducerea vârfurilor - păstrând în același timp limbajul permis de acest grafic de tranziție:

a) reducerea coastelor:

B ) reducerea vârfurilor (înlocuirea se efectuează pentru fiecare cale care trece prin vârful p, urmată de eliminarea acestuia ca stare de neatins):

Evident, fiecare operație de reducere nu schimbă limbajul recunoscut de graficul de tranziție, ci reduce fie numărul de muchii, fie numărul de vârfuri, iar în final reducerile vor aduce graficul de tranziție la forma prezentată în Fig. 2. Teorema este dovedită: fiecare limbaj automat este o mulțime obișnuită.

Exemplu

Fie dată mașina finită A:

Construim un grafic de tranziție echivalent într-o formă normalizată.

Reducerea vârfurilor 3:

Reducerea arcurilor și aplicarea regulii R = R:

Reducerea vârfurilor 2:

Reducerea arcului și vârfului 1:

Astfel, limbajul recunoscut de automatul A este dat de expresia regulată: R A = b+(a+bb)(b+ab)*a.

Să demonstrăm teorema lui Kleene în cealaltă direcție.

Teorema 2.Fiecare set obișnuit este un limbaj automat: R A.

Dovada. Să arătăm că pentru fiecare expresie regulată R se poate construi un automat finit A r (posibil nedeterminist) care să recunoască limbajul specificat de R. Vom defini recursiv astfel de automate.

(starea inițială și finală a lui A sunt combinate).

Exemplu(continuare)

Teoria automatelor - aceasta este o secțiune a teoriei sistem de control, studiind modele matematice ale convertoarelor de informații discrete, numite mitraliere. Dintr-un anumit punct de vedere, astfel de convertoare sunt atât dispozitive reale (calculatoare, automate, organisme vii etc.), cât și sisteme abstracte (de exemplu, un sistem formal, teorii axiomatice etc.), făcând posibilă aplicarea teoriei automate în diverse cercetări științifice și aplicate. Teoria automatelor este cel mai strâns legată de logica matematică și teoria algoritmilor. În special, solvabilitatea unor calcule formale este dovedită folosind mijloacele teoriei automatelor.

Un alt subiect important de studiu al acestui curs este limbaj formal 1 – un set arbitrar de cuvinte dintr-un anumit alfabet. Importanța limbajelor formale pentru informatica teoretică se datorează faptului că cel mai simplu și mai convenabil model de date utilizat în programele de calculator este o secvență finită, fiecare element fiind preluat dintr-o mulțime finită prefixată. Deoarece limbajele formale utilizate în aplicații sunt de obicei infinite, este necesară o modalitate de a descrie limbajul formal într-o manieră finită. În acest curs vom studia 3 mijloace clasice ale acestei descrieri: mitraliere, expresii obisnuiteȘi gramatici generative.

Introducere

1. Concepte de bază ale teoriei limbajelor formale

Luați în considerare o mulțime finită nevidă A, format din caractere ( A 1 , …, A k). Vom suna A alfabet , iar simbolurile sale sunt scrisori . Orice succesiune finită de litere ale acestui alfabet este numită intr-un cuvant (lanţ sau linia ): w=A 1 A 2 …A n- cuvânt ( A i A), |w| – lungimea cuvântului (numărul de litere care alcătuiesc cuvântul, fiecare caracter apare de câte ori apare în w). Prin | w| b indicați numărul de apariții ale simbolului b pe cuvânt w.

Secvență infinită de litere din alfabet A numit supercuvânt , - un supercuvânt dintr-un număr infinit de litere A. Gol este un cuvânt care nu conține o singură literă. Se notează cu . Evident ||=0.

- multe cuvinte din alfabet A lungime n. Set de toate cuvintele alfabetului A(inclusiv supercuvinte) este indicat A*. Această mulțime este numărabilă deoarece este uniunea unui număr numărabil de mulțimi finite
. Setul tuturor cuvintelor negoale din alfabet A notat cu A+ . Dacă A={A), Acea A*={A)* va fi notat cu A*.

Orice subset
numit limbă (limbaj formal ) deasupra alfabetului A.

Dacă XȘi y– cuvintele limbii
, apoi cuvântul X y(rezultatul atribuirii cuvântului la la sfârşitul unui cuvânt X) se numește concatenare (ambreiaj , muncă ) cuvinte XȘi la.
(n hai să o luăm o dată X). Sa punem
.

Ei spun că cuvântul X – subcuvânt cuvinte la, Dacă y=uxv pentru câteva cuvinte uȘi v. Toate subcuvintele cuvintelor din limbă
formă multe subcuvinte limba L, care este notat cu Subw( L).

Exemple. 1. ba 3 =baaa,
- acest cuvânt are subcuvinte ab, aba, bași așa mai departe.

2. Setați ( A, abb) - limba (finală) peste alfabet ( A, b}.

3. Loturi
este o limbă deasupra alfabetului ( A, b). Acest limbaj este nesfârșit, conține cuvinte b, ba, aba, baa, abaa, baaa, aabaa, abaaa etc.

Întrucât fiecare limbă este un set, putem lua în considerare operațiile de unire, intersecție și diferență ale limbilor definite pe același alfabet. Da, limbaj
, Unde
, numit complement al limbajului L referitor la alfabet A. Și dacă  este întotdeauna inclus în A*, apoi limba
poate conţine sau nu . In ultimul caz
.

Lăsa ,
. Apoi se numește limbajul concatenare (ambreiaj , muncă ) limbi Și . în care
,
(n ori) dacă n>0.

Exemple. 1. Dacă
,
,Acea .

2. Dacă L=(0, 01), atunci
.

Repetare limba L numit limbaj
(această operație se mai numește Asterisc Kleene ). Limba
numit iterație pozitivă limba L.

Exemplu. Dacă A={A, b) Și L={aa, ab, ba, bb), Acea
.

Prin apel sau într-o imagine în oglindă cuvinte w cuvântul se numește w R, în care literele cuvântului w mergi in ordine inversa. De exemplu, dacă w=bac, Acea

Lăsa
. Apoi limba
numit recurs limba L.

Vom numi fiecare început de cuvânt prefix , și fiecare sfârșit al unui cuvânt - sufix . De exemplu, dacă y=xv, Acea X– prefix de cuvânt la(denumirea – X[y), A v– sufix de cuvânt la(denumirea – v]y). Evident, cuvântul gol este atât un prefix, cât și un sufix al oricărui cuvânt. Toate prefixele cuvintelor din limbă
formă multe prefixe din această limbă: Pref( L)
. Similar cu Suf( L)
-m cuțit de sufixe limba
.

Dacă limba L nu este nici un cuvânt L nu este un prefix (sufix) al niciunui alt cuvânt L, atunci ei spun asta L are prefix (sufix) proprietate .

Lăsa A 1 și A 2 – alfabete. Dacă se afișează f:
satisface condiția pentru toate cuvintele
Și
, apoi cartografierea f numit homomorfism .

Note. 1. Se poate dovedi că dacă f este un homomorfism, atunci
.

2. Omomorfismele nu sunt întotdeauna bijecții, dar fiecare homomorfism este determinat în mod unic de semnificațiile sale pe cuvinte cu o singură literă.

3. Aplicarea homomorfismului la limbaj L, obținem o altă limbă f(L).

Dacă f:
- homomorfism,
Și
, apoi prin f(L 1) este indicată limba
, și prin
limba este indicată
, și afișajul în sine
numit inversarea homomorfismului .

Exemple. 1. Să presupunem că vrem să înlocuim fiecare apariție a caracterului 0 din șir cu caracterul A, iar fiecare apariție a lui 1 este activată bb. Apoi putem defini un homomorfism f Asa de
Și
. Dacă
, Acea
.

2. Lasă f este un homomorfism pentru care
Și
. Apoi
Și
.

În acest capitol începem să prezentăm elementele teoriei limbajelor formale.

Când spunem „limbaj formal”, ne referim la faptul că rezultatele prezentate aici sunt folosite în primul rând pentru a descrie limbaje artificiale inventate de oameni în scopuri speciale, cum ar fi limbaje de programare. Dar nu există nicio barieră de netrecut între limbile artificiale (formale) special inventate și limbajele naturale care apar și se dezvoltă spontan. Se pare că limbile naturale sunt caracterizate de reguli gramaticale complexe, adică. sunt destul de rigid formalizate și chiar și cel mai „dezvoltat științific” limbaj de programare conține „locuri întunecate”, a căror înțelegere fără ambiguitate este o problemă.

Există trei aspecte principale de care trebuie să țineți cont atunci când învățați limbi străine.

Primul este sintaxa limbajului . O limbă este un fel de set de „cuvinte”, unde un „cuvânt” este o anumită secvență finită de „litere” - simboluri ale unui alfabet prefixat. Termenii „scrisoare” și „cuvânt” pot fi înțeleși în moduri diferite (definiția matematică a acestor termeni va fi dată mai jos). Astfel, „litere” pot fi de fapt litere din alfabetul unui limbaj natural sau formal, de exemplu, limba rusă sau limbajul de programare Pascal. Apoi „cuvintele” vor fi secvențe finite de „litere”: crocodil, „ întreg". Asemenea cuvinte se numesc "lexeme". Dar o "litera" poate fi un "cuvânt" ("lexem") în ansamblu. Atunci "cuvintele" sunt propoziții dintr-un limbaj natural sau programe de limbaj de programare. Dacă un anumit set de „litere” este fix, atunci nu fiecare secvență a acestora va fi un „cuvânt”, adică un „Elexem” al unei anumite limbi, ci doar o secvență care respectă anumite reguli. Cuvântul „krykadil” nu este un lexem în rusă, iar cuvântul „iff” nu este un lexem în Pascal. Propoziția „Te iubesc” nu este o propoziție corectă în limba rusă, la fel cum notația „x:= =t” nu este un operator de atribuire Pascal scris corect. Sintaxa* unei limbi este un sistem de reguli în conformitate cu care se pot construi secvențe „corecte” de „litere”. Fiecare cuvânt al unei limbi este caracterizat de o anumită structură specifică acelei limbi. Apoi este necesar, pe de o parte, să se dezvolte mecanisme de enumerare sau generare a cuvintelor cu o structură dată, iar pe de altă parte, mecanisme de verificare a apartenenței unui anumit cuvânt unei limbi date. În primul rând, aceste mecanisme sunt studiate de teoria clasică a limbajelor formale.

Al doilea aspect - semantica limbajului . Semantica** presupune asocierea cuvintelor unei limbi cu un anumit „sens,” Sens.” De exemplu, atunci când scriem o formulă matematică, trebuie să respectăm anumite reguli sintactice (plasarea parantezelor, ortografia simbolurilor, ordinea simbolurilor etc. ), dar, în plus, formula are un sens foarte definit, înseamnă ceva.

Limba este un mijloc de comunicare și transmitere a informațiilor. Dacă vrem să fim înțeleși, trebuie nu doar să ne construim corect sintactic vorbirea, respectând ordinea corectă a literelor dintr-un cuvânt și cuvintelor dintr-o propoziție, ci trebuie să ne preocupe și de sensul lui, de ideile pe care le exprimăm în vorbire. Teoriile matematice ale „sensului” au apărut relativ recent și, pe lângă capitolul următor, vom analiza foarte pe scurt câteva abordări ale descrierii matematice a semanticii limbajelor de programare.

* Cuvântul „sintaxă” provine din greaca veche „syn” - „împreună” și „taxis” - „ordine, structură”. Astfel, sintaxa poate fi înțeleasă ca „compunere”.

** Din cuvintele grecești antice „sema” - „semn, semn” și „semanticos” - „desemnând”.

În sfârșit, al treilea aspect - pragmatica limbajului . Pragmatica este asociată cu scopurile pe care un vorbitor nativ și le stabilește: de exemplu, o persoană pronunță un discurs cu scopuri legate nu de sintaxă, nu de semantica limbii în care vorbește sau scrie, ci, să zicem, de a primi un anumită sumă de bani pentru discursul lui.sume de bani. Pragmatica este mai degrabă o disciplină socio-filozofică, care afectează activitatea de stabilire a scopurilor individului. Nu o vom atinge deloc.

Acest capitol va examina mai întâi conceptele de bază ale teoriei matematice a limbajelor formale, dintre care cel mai important este conceptul de gramatică generativă, iar apoi așa-numitele limbaje regulate. Teoria limbajelor regulate, împreună cu teoria automatelor finite, formează fundamentul întregii teorii a limbajelor formale.

• Alfabet, cuvânt, limbă

• Gramaticile generative

  După cum sa menționat deja, teoria clasică a limbilor formale studiază în primul rând sintaxa limbajului. Introduce un model matematic de sintaxă care descrie mecanismele de generare și recunoaștere a lanțurilor „bine formate”. În această secțiune ne vom uita la primul dintre aceste mecanisme.

Lucrare de laborator nr 3

Dezvoltarea unui analizator lexical este destul de simplă dacă se utilizează teoria limbajelor obișnuite și a automatelor finite. În cadrul acestei teorii, clasele de lexeme de același tip sunt considerate limbaje formale (limbajul identificatorilor, limbajul constantelor etc.), al căror set de propoziții este descris folosind gramatica generativă corespunzătoare. În plus, aceste limbi sunt atât de simple încât sunt generate de cea mai simplă dintre gramatici - gramatica obișnuită.

Definiția 1. gramatica generativa G = , ale căror reguli au forma: A::=aB sau C::=b, unde A, B, C Є N; a, b Є Т se numește regulat (automat).

Limbajul L (G) generat de o gramatică automată se numește limbaj automat (regulat) sau un limbaj cu un număr finit de stări.

Exemplul 1. O clasă de identificatori, dacă identificatorul este o secvență formată din litere și cifre, iar primul caracter al identificatorului poate fi doar o literă, este descrisă de următoarea gramatică regulată generativă G = , în care

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

P = ( 1. I::= b

Aici b, c sunt simboluri terminale generalizate pentru desemnarea literelor și, respectiv, numerelor.

Procesul de generare a identificatorului „bbcbc” este descris de următoarea secvență de substituții

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

Cu toate acestea, sarcina principală a LA nu este generarea de unități lexicale, ci recunoașterea lor. Modelul matematic al procesului de recunoaștere a unui limbaj obișnuit este un dispozitiv de calcul numit mașină cu stări finite (FA). Termenul „finit” subliniază faptul că dispozitivul de calcul are o cantitate fixă ​​și finită de memorie și procesează o secvență de simboluri de intrare aparținând unei mulțimi finite. Există diferite tipuri de KA, dacă funcția de ieșire KA (rezultatul muncii) este doar o indicație a faptului că secvența de intrare a simbolurilor este acceptabilă sau nu, un astfel de KA se numește rezolutor final.

Definiția 2. Următoarele cinci se numesc un automat finit:

A = , unde V = (a 1 , a 2 , …, a m ) – alfabet de intrare (set finit de simboluri);

Q = (q 0 , q 1 , …, q n -1 ) – alfabetul stărilor (set finit de simboluri);

δ: Q ×V →Q – funcție de tranziție;

q 0 Є Q – starea inițială a automatului finit;

F Є Q – set de stări finale.

Schema de funcționare a navei spațiale.

Există o bandă infinită, împărțită în celule, fiecare dintre acestea putând conține un simbol din V. Lanțul α Є V* este scris pe bandă. Celulele din stânga și dreapta lanțului sunt goale. Există un dispozitiv de control final (FCU) cu un cap de citire, care poate citi secvenţial caracterele de pe bandă, deplasându-se de-a lungul benzii de la stânga la dreapta. În acest caz, unitatea de control poate fi în orice stare din Q. Unitatea de control își începe întotdeauna activitatea în starea inițială q 0 și se termină într-una dintre stările finale F. De fiecare dată, se trece la o nouă celulă pe bandă, unitatea de control intră într-o stare nouă în conformitate cu funcția δ.

Funcția de tranziție a navei spațiale poate fi reprezentată în următoarele moduri:

· Un set de echipe;

· Diagrama de stare;

· Tabel de tranziție.

Comanda mașinii de stări este scrisă după cum urmează:

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

Această comandă înseamnă că mașina de stări este în starea q i, citește simbolul a j de pe bandă și trece în starea q k.

Grafic, comanda este reprezentată ca un arc grafic care merge de la vârful q i la vârful q k și marcată cu simbolul a j al alfabetului de intrare:

Reprezentarea grafică a întregii mapări δ se numește diagramă de stări a unei mașini cu stări finite.

Dacă nava spațială se găsește într-o situație (q i, a j), care nu este partea stângă a niciunei comenzi, atunci se oprește. Dacă unitatea de control numără toate simbolurile lanțului α înregistrate pe bandă și, în același timp, trece la starea finală q r Є F, atunci ei spun că lanțul α este permis de mașina cu stări finite.

Tabelul de tranziție a navei spațiale este construit după cum urmează: coloanele matricei corespund simbolurilor din alfabetul de intrare, rândurile corespund simbolurilor din alfabetul de stare, iar elementele matricei corespund stărilor în care intră nava spațială pentru o anumită combinație de simboluri de intrare. și simbol de stat.

Fie o gramatică regulată G = , ale căror reguli au forma: A i::= a j A k sau A i::= a j, unde A i, A k Є N și a j Є T.

Atunci automatul finit A = , admițând același limbaj pe care îl generează gramatica obișnuită G, se construiește după cum urmează:

2) Q = N U (Z), Z N și Z T, Z este starea finală a navei spațiale;

5) Maparea δ este construită sub forma:

· Fiecare regulă de substituție din gramatica G de forma A i::= a j A k este asociată cu comanda (A i, a j) → A k;

· Fiecare regulă de substituție de forma A i::= a j este asociată cu comanda (A i, a j) → Z;

Exemplul 2. Construiți un CA pentru gramatica din exemplul 1. Avem A = , Unde

1) V = T = (b, c)

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

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

5) δ: a) sub forma unui set de comenzi:

b) sub forma unei diagrame de stare

Există mașini cu stări finite deterministe și nedeterministe. Nava spațială se numește nedeterminist KA (NKA), dacă în diagrama sa de stare mai multe arce cu semne identice emană dintr-un vârf. De exemplu, KA din exemplul 2 este un NKA.

În scopuri practice, este necesar ca dispozitivul de recunoaștere final să determine însuși momentul sfârșitului secvenței de introducere a caracterelor și să emită un mesaj despre corectitudinea sau eroarea secvenței de introducere. În aceste scopuri, lanțul de intrare este considerat limitat în dreapta de marcatorul de capăt ├ și stările interpretate sunt introduse în diagrama de stări a navei spațiale:

Z – „permite lanțul de intrare”;

O – „a fost memorată o eroare în lanțul de intrare”;

E – „respingeți lanțul de intrare”.

Stările Z și E sunt finale, iar nava spațială merge la ele când citește marcatorul de sfârșit ├, respectiv, după procesarea unui lanț de intrare corect sau eronat. Starea O este intermediară, nava spațială trece în ea din orice stare validă a navei spațiale atunci când este detectată o eroare în lanțul de intrare și rămâne acolo până când sosește markerul de sfârșit ├, după care trece la starea E - „respinge lanțul de intrare. ”