Gramatica formală

Gramaticile formale sunt modele matematice ale gramaticilor care sunt utilizate pentru a genera și descrie în mod unic limbaje formale . Acestea sunt utilizate în informatică teoretică , în special în teoria calculabilității , și în construcția compilatorului, pe de o parte, pentru a determina în mod clar dacă un cuvânt este un element al unui limbaj și, pe de altă parte, pentru a investiga sau a dovedi proprietățile acestor formale. limbi. Gramaticile formale sunt clasificate folosind sistemele Semi-Thue date în ierarhia Chomsky .

Descriere

Cu o gramatică formală, începând de la un simbol de început ( numită și variabilă de început ), regulile de producție pot fi aplicate dintr-un set de reguli, care generează șiruri de caractere ( cuvinte ) noi din simbolul de început , care la rândul lor pot fi înlocuite în continuare. Acest proces se mai numește derivare . ${\ displaystyle S}$${\ displaystyle P}$

Vocabularul unei gramatici, constând în unirea disjunctă a unui alfabet de simboluri terminale cu un set de simboluri non-terminale , specifică ce simboluri pot fi utilizate pentru aceasta. Setul de simboluri terminale definește ce caractere sunt alcătuite din cuvinte care nu pot fi derivate în continuare. Luate împreună, aceste cuvinte alcătuiesc limbajul formal descris de gramatică. Simbolul de start, pe de altă parte, trebuie să fie un simbol non-terminal. Simbolurile non-terminale suplimentare permit reguli mai diferențiate. ${\ displaystyle V}$ ${\ displaystyle T}$ ${\ displaystyle N}$

Prin definiție, regulile de producție sunt perechi ordonate care sunt, de asemenea, scrise. Se aplică unui șir înlocuind o apariție a șirului în cu . În partea stângă a regulii trebuie să existe întotdeauna cel puțin un simbol non-terminal. O mulțime de reguli cu aceeași parte stângă, care este , de asemenea , sunt abreviat ca . ${\ displaystyle (\ alpha, \ beta)}$${\ displaystyle \ alpha \ rightarrow \ beta}$${\ displaystyle w}$${\ displaystyle \ alpha}$${\ displaystyle w}$${\ displaystyle \ beta}$${\ displaystyle \ alpha \ rightarrow \ beta _ {1}, \; \ ldots, \ alpha \ rightarrow \ beta _ {n}}$${\ displaystyle \ alpha \ rightarrow \ beta _ {1} \; | \; \ ldots \; | \; \ beta _ {n}}$

De exemplu, se poate utiliza setul de reguli pentru fiecare deriva sau să obțină șirul . ${\ displaystyle X \ rightarrow + \; | \; -}$${\ displaystyle 1X2}$${\ displaystyle 1 + 2}$${\ displaystyle 1-2}$

Așa cum mai multe reguli pot fi aplicabile unui șir dat, nu trebuie să existe întotdeauna doar un singur loc în șirul pe care se potrivește o regulă. Gramaticile formale nu dictează nicio ordine. Toate cuvintele care constau numai din simboluri terminale care pot fi derivate din simbolul de început se numără în limbajul descris de gramatică.

definiție

O gramatică formală este reprezentată de 4- tuplu , în care:${\ displaystyle G = (V, T, P, S)}$

• ${\ displaystyle V}$, un set finit de simboluri , care se numește set de simboluri sau vocabular ,
• ${\ displaystyle T \ subset V}$, un subset de , numit și alfabet și ale cărui elemente se numesc simboluri terminale ,${\ displaystyle V}$
• ${\ displaystyle P \ subset \ left (V ^ {*} \ setminus T ^ {*} \ right) \ times V ^ {*}}$, un set finit de reguli de producție , de asemenea
• ${\ displaystyle S \ în V \ setminus T}$, simbolul de start .

Aici, corpul navei Kleenesche reprezintă un set de caractere (sau cuvinte). ${\ displaystyle X ^ {*}}$${\ displaystyle X}$

Setul este setul de simboluri neterminal ( de asemenea , numit neterminal sau metasymbols ), în special caracterul de start aparține. Cuvântul din partea stângă a perechilor de reguli nu trebuie să fie format exclusiv din caractere terminale, care pot fi exprimate și printr-o concatenare : ${\ displaystyle N = V \ setminus T}$

${\ displaystyle \ left (V ^ {*} \ setminus T ^ {*} \ right) = V ^ {*} NV ^ {*}}$.

Nu are prea mult sens dacă cuvântul din dreapta are simbolul de început. Unii autori iau în considerare acest lucru prin restricționarea corespunzătoare a setului asociat, i. H. prin înlocuire. ${\ displaystyle V ^ {*}}$${\ displaystyle (V \ setminus \ {S \}) ^ {*}}$

Unii autori se referă alternativ la cvadruplu ca gramatică . Există, de asemenea, următoarele denumiri diferite:${\ displaystyle (N, T, P, S)}$${\ displaystyle G}$

• ${\ displaystyle \ Sigma}$pentru caracterele terminale , aici ,${\ displaystyle T}$
• ${\ displaystyle \ Sigma}$pentru întregul vocabular ( set de simboluri ) al tuturor simbolurilor , aici ,${\ displaystyle V}$
• ${\ displaystyle V}$pentru caracterele non-terminale ( variabile ), aici ,${\ displaystyle N}$
• ${\ displaystyle \ lambda}$pentru cuvântul gol, aici .${\ displaystyle \ epsilon}$

Limbajul descris de o gramatică

O regulă a unei gramatici date spune că într-un cuvânt cu R ca infix , R poate fi înlocuit cu Q, astfel încât să fie creat un nou cuvânt cu un infix. Se vorbește, de asemenea, despre faptul că în trece peste gramatică sau prin regulă , sau că a fost derivat din. Acest lucru poate fi notat prin (adesea în loc de ). Dacă trebuie exprimat doar că cuvântul de la poate apărea în gramatică fără a denumi o regulă, se scrie în schimb ( dacă gramatica este evidentă din context, de asemenea simplă ). În consecință, o astfel de tranziție de la o relație de tranziție este o extensie naturală a tuturor contextelor posibile , și anume: ${\ displaystyle R \ rightarrow Q \ în P}$${\ displaystyle G}$${\ displaystyle w \ in V ^ {\ ast}}$${\ displaystyle w ^ {\ prime}}$${\ displaystyle Q}$${\ displaystyle w}$${\ displaystyle w ^ {\ prime}}$${\ displaystyle G}$${\ displaystyle R \ rightarrow Q}$${\ displaystyle w ^ {\ prime}}$${\ displaystyle w}$${\ displaystyle w \ rightsquigarrow _ {R \ rightarrow Q} w ^ {\ prime}}$${\ displaystyle \ Rightarrow}$${\ displaystyle \ rightsquigarrow}$${\ displaystyle G}$${\ displaystyle w ^ {\ prime}}$${\ displaystyle w}$${\ displaystyle w \ rightsquigarrow _ {G} w ^ {\ prime}}$${\ displaystyle w \ rightsquigarrow w ^ {\ prime}}$${\ displaystyle w}$${\ displaystyle w ^ {\ prime}}$${\ displaystyle P}$${\ displaystyle V ^ {*}}$

${\ displaystyle \ rightsquigarrow \ ;: = \; \ {(u \ circ R \ circ v, u \ circ Q \ circ v) | (R, Q) \ in P, u, v \ in V ^ {*} \}}$,

în cazul în care aici reprezintă concatenarea cuvintelor. ${\ displaystyle \ circ}$

Dacă există o succesiune de cuvinte în care este adevărat că pentru fiecare număr natural cu cuvântul în trece peste ( ), atunci ceea ce este reprezentat prin poate fi derivat în pași de la . O astfel de secvență de cuvinte se numește un derivat sau calcul al în lungime . Mai mult, în mijloace derivabile dacă există cel puțin unul astfel încât să poată fi derivat în pași de la . Dacă în poate fi derivat, aceasta este reprezentată de notație . Acesta este definit în plus , că pentru fiecare cuvânt , care este, astfel că relația este plicul reflexiv-tranzitivă a relației . ${\ displaystyle w_ {0}, w_ {1}, \ ldots, w_ {n} \ în V ^ {\ ast}}$${\ displaystyle i}$${\ displaystyle 0 \ leq i <n}$${\ displaystyle w_ {i}}$${\ displaystyle w_ {i + 1}}$${\ displaystyle w_ {i} \ rightsquigarrow _ {G} w_ {i + 1}}$${\ displaystyle w_ {n}}$${\ displaystyle n}$${\ displaystyle w_ {0}}$${\ displaystyle w_ {0} \ rightsquigarrow _ {G} ^ {n} w_ {n}}$${\ displaystyle w_ {0}, w_ {1}, \ ldots, w_ {n}}$${\ displaystyle w_ {0}}$${\ displaystyle w_ {n}}$${\ displaystyle n}$${\ displaystyle w}$${\ displaystyle w ^ {\ prime}}$${\ displaystyle n \ in \ mathbb {N} _ {0}}$${\ displaystyle w ^ {\ prime}}$${\ displaystyle n}$${\ displaystyle w}$${\ displaystyle w}$${\ displaystyle w ^ {\ prime}}$${\ displaystyle w \ rightsquigarrow _ {G} ^ {\ ast} w ^ {\ prime}}$${\ displaystyle w \ in V ^ {\ ast}}$${\ displaystyle w \ rightsquigarrow _ {G} ^ {\ ast} w}$${\ displaystyle \ rightsquigarrow _ {G} ^ {\ ast}}$${\ displaystyle \ rightsquigarrow _ {G}}$

Acum, limbajul formal generat de gramatică este limbajul care constă din toate cuvintele care, pe de o parte, constau doar din simboluri terminale și, pe de altă parte, pot fi derivate din simbolul de început cu un număr finit de pași: ${\ displaystyle G}$${\ displaystyle L (G)}$

${\ displaystyle L \ left (G \ right): = \ left \ {w \ in T ^ {*} | S \ rightsquigarrow _ {G} ^ {*} w \ right \}}$

Nu contează în ce ordine sunt aplicate regulile de producție cuvintelor derivate sau dacă există mai multe opțiuni pentru derivarea unui cuvânt . Două gramatici și sunt echivalente dacă și numai dacă limbile generate de și sunt egale: ${\ displaystyle w}$${\ displaystyle S}$${\ displaystyle G_ {1}}$${\ displaystyle G_ {2}}$${\ displaystyle G_ {1}}$${\ displaystyle G_ {2}}$

${\ displaystyle G_ {1} \ mathrm {\ este \ {\ ddot {a}} echivalent \ cu \} G_ {2}: \ Longleftrightarrow L (G_ {1}) = L (G_ {2})}$

Dacă toate caracterele terminale apar în cuvintele limbajelor formale, atunci caracterele terminale trebuie să se potrivească. Caracterele non-terminale, pe de altă parte, sunt complet gratuite.

Exemple

${\ displaystyle G_ {1}}$fie o gramatică cu simbolurile terminale , simbolurile non-terminale , simbolul de început și cu regulile ${\ displaystyle \ {a, b \}}$${\ displaystyle \ {S, A, B \}}$${\ displaystyle S}$

${\ displaystyle {\ begin {matrix} S & \ to & ABS & \, (1) \\ S & \ to & \ varepsilon & \, (2) \\ BA & \ to & AB & \, (3) \\ BS & \ to & b & \, (4) \\ Bb & \ to & bb & \, (5) \\ Ab & \ to & ab & \, (6) \\ Aa & \ to & aa & \, (7) \ end {matrix}}}$

Aici este cuvântul gol , care este un cuvânt de lungime 0. Această gramatică definește limbajul tuturor cuvintelor formei cu . Deci, din cauza următoarelor derivațiile, cuvintele , și elemente ale limbii descrise de către : ${\ displaystyle \ varepsilon}$${\ displaystyle G_ {1}}$${\ displaystyle a ^ {n} b ^ {n}}$${\ displaystyle n \ in \ mathbb {N} _ {0}}$${\ displaystyle \ varepsilon}$${\ displaystyle from}$${\ displaystyle aabb}$${\ displaystyle G_ {1}}$

• ${\ displaystyle S \ rightsquigarrow \ varepsilon}$, folosind regula (2),
• ${\ displaystyle S \ rightsquigarrow ABS \ rightsquigarrow Ab \ rightsquigarrow ab}$, prin intermediul regulilor (1), (4) și (6),
• ${\ displaystyle S \ rightsquigarrow ABS \ rightsquigarrow ABABS \ rightsquigarrow ABAb \ rightsquigarrow AABb \ rightsquigarrow AAbb \ rightsquigarrow Aabb \ rightsquigarrow aabb}$, prin intermediul regulilor (1), (1), (4), (3), (5), (6) și (7).

Dar există și alte modalități de a obține cuvântul din . ${\ displaystyle aabb}$${\ displaystyle S}$

O altă gramatică care descrie aceeași limbă este gramatica fără context, cu regulile: ${\ displaystyle G_ {2}}$${\ displaystyle {\ begin {matrix} S & \ to & aSb \ | \ \ varepsilon \ end {matrix}}}$

Fiecare limbaj recursiv enumerabil este generat de mai multe gramatici ( numărabile, infinit multe ). Cu toate acestea, există și limbi care nu pot fi generate de nicio gramatică.

Clasele de gramatică

Gramaticile sunt alocate claselor care se caracterizează prin asemănări. Cea mai cunoscută clasificare a fost descrisă de Noam Chomsky și Marcel Schützenberger folosind ierarhia Chomsky .

Ierarhia Chomsky

Ierarhia Chomsky împarte gramaticile în clase de tip 0 la tip 3 în funcție de tipul de norme de producție:

• Gramaticile de tip 0: gramaticile structurii frazelor sunt gramatici formale nelimitate.
• Gramaticile de tip 1: gramaticile sensibile la context pot consta doar din reguli în care exact un simbol non-terminal este înlocuit cu un șir de caractere. Acest simbol poate fi, de asemenea, înconjurat de alte simboluri în partea stângă a regulii, care indică un context în care trebuie să aibă loc înlocuirea.
• Gramaticile de tip 2: în gramaticile fără context , pe de altă parte, poate exista doar un simbol non-terminal în partea stângă a regulilor. Simbolul poate fi apoi înlocuit indiferent de context.
• Gramaticile de tip 3: În cazul gramaticilor obișnuite , laturile din stânga regulilor conțin, de asemenea, doar un simbol non-terminal. În gramaticile obișnuite din stânga, partea dreaptă a regulii poate consta din cel mult un simbol non-terminal urmat de cel mult un simbol terminal (de exemplu ). La gramatici destul de regulate de altă parte, în partea dreaptă a maximum un simbol terminal poate exista, cel mai urmeaza un neterminal (Ex:. ).${\ displaystyle X \ to Ya}$${\ displaystyle X \ to aY}$

Clasele de limbă asociate sunt în scădere în dimensiune. Există următoarea relație reală de incluziune :

Pentru clasele de limba în funcție de tipul cu următoarele se aplică: . ${\ displaystyle L_ {n}}$${\ displaystyle n}$${\ displaystyle n \ in \ {0,1,2,3 \}}$${\ displaystyle L_ {3} \ subset L_ {2} \ subset L_ {1} \ subset L_ {0}}$

Alte cursuri de limbă

În afară de ierarhia Chomsky, s-au stabilit și alte clase de gramatică:

• Gramaticile monotone descriu aceeași clasă de limbă ca gramaticile sensibile la context. Gramaticile din ce în ce mai sensibile la context care descriu o subclasă a clasei de limbaj contextual sunt oarecum mai stricte .
• Gramaticile fără context determinist descriu limbajele deterministe fără context . Acestea sunt, de asemenea, descrise de gramaticile LR (k) , care sunt importante pentru compilarea compilatoarelor. Alte gramatici cunoscute în construcția compilatorului sunt gramaticile LL (k) și gramaticile LF (k) .

Vezi si

• Gramatică grafică
• Backus-Naur-Form și Extended Backus-Naur-Form
• Teoria sintaxei asupra gramaticilor (formale) din lingvistică
• Comunicarea sistemului gramatical

literatură

• Katrin Erk, Lutz Priese: Informatică teoretică. O introducere cuprinzătoare . A doua ediție extinsă. Springer-Verlag, Berlin și colab. 2002, ISBN 3-540-42624-8 , pp. 53-61 . 

Link-uri web

• Site-ul Gramatic

Dovezi individuale

1. ↑ Peter Bachmann: Fundamentele teoriei computerizate . Cottbus 2001, p. 47 ( PDF [accesat la 12 februarie 2011] note de curs). 
2. ↑ În timp ce semnificația și sau în cazul dat este clară, trebuie să clarificați ce se înțelege cu (precum și cel frecvent utilizat ) verificând contextul; în cazul în care-o de patru ori gramatica la care nu pot părăsi.${\ displaystyle T, N}$${\ displaystyle \ epsilon}$${\ displaystyle \ lambda}$${\ displaystyle V}$${\ displaystyle \ Sigma}$
3. ↑ ^{a b} Klaus Reinhardt: Mașini de plată cu prioritate și sincronizarea limbilor autoșenilă ( amintire originalului din 17 ianuarie 2018 în Internet Archive ) Info: Arhiva link a fost inserat și nu în mod automat încă verificată. Vă rugăm să verificați linkul original și arhivă conform instrucțiunilor și apoi eliminați această notificare. , Facultatea de Informatică de la Universitatea din Stuttgart; Teza de doctorat 1994. Cvadruplul gramatical este literalmente specificat aici, ceea ce înseamnă în denumirea aleasă aici . @ 1@ 2Șablon: Webachiv / IABot / users.informatik.uni-halle.de${\ displaystyle (V, \ Sigma, P, S)}$${\ displaystyle (N, T, P, S)}$