În matematică , informatică și lingvistică , un limbaj formal este un set de cuvinte . Alfabetul unui limbaj formal este ansamblul de simboluri, litere sau lexeme care sunt folosite pentru a construi cuvintele limbii; adesea, se presupune că acest alfabet este terminat. Teoria limbaje formale are ca scop descrierea limbilor formale.
Cuvintele sunt secvențe ale elementelor acestui alfabet; cuvintele care aparțin unui anumit limbaj formal sunt uneori numite cuvinte bine formate sau formule bine formate . Un limbaj formal este adesea definit de o gramatică formală , cum ar fi gramaticile algebrice, și analizat prin automate .
Teoria limbajelor formale studiază aspectele pur sintactice ale acestor limbaje, adică structura lor formală internă. Teoria limbajului provine din lingvistică , ca mijloc de înțelegere a regulilor sintactice ale limbilor naturale :
Studiul limbajelor formale include toate mijloacele de descriere și analiză a acestor limbi, cum ar fi gramaticile formale pentru generare și automatele pentru recunoaștere, dar este interesat și de învățarea automată și traducere . În domeniul traducerii, teoria limbajului se aplică compilatoarelor de limbaj de programare.
Ne oferim un set , numit alfabet ale cărui elemente se numesc litere .
Această lege a compoziției interne este asociativă și admite cuvântul gol pentru element neutru (care justifică notația ). În consecință, setul , prevăzut cu această lege, este un monoid . Este un monoid liber în sensul algebrei.
Un limbaj formal este un set de cuvinte pe un alfabet finit, adică o parte a monoidului liber de pe acest alfabet.
Câteva exemple de limbaje formale:
Un limbaj formal poate fi specificat prin diferite mijloace. Ceea ce se caută este o metodă sau mecanism finit și explicit care face posibilă producerea sau analiza unui limbaj în general infinit. Printre aceste metode, există:
Întrebările tipice pe care ni le punem despre un limbaj formal sunt următoarele:
Aceste întrebări au legături cu teoria calculabilității și complexității .
Limbile sunt grupate în familii de limbi. Ierarhia Chomsky ne oferă patru tipuri de gramatică, fiecare tip de gramatică generând o familie de limbi.
Aceste seturi de limbi sunt toate incluse unul în celălalt și sunt date aici de la cel mai mare set la cel mai mic. Deci, orice limbaj rațional este algebric , care este el însuși contextual , care este el însuși recursiv enumerabil .
Între aceste 4 familii de limbi, se pot remarca familii care nu fac parte din ierarhia Chomsky, dar care rămân remarcabile prin definițiile și proprietățile lor. Cele deterministe Limbile libere de context sunt limbile recunoscute de automate stivă deterministe , și sunt strict incluse în familia limbilor algebrice. Cele Limbile recursive sunt limbile recunoscute de o mașină Turing, și a cărui completare este , de asemenea , recunoscut de o mașină Turing. Prin urmare, acestea sunt strict incluse în limbile recursiv enumerabile .
Mai multe operații pot fi utilizate pentru a crea limbi noi din limbi date. Să presupunem că L și M sunt limbi pe un anumit alfabet comun.
Intersecția operațiunilor setului , unirea și complementarea sunt definite ca pentru orice set.
Concatenarea de L și M , tocmai a remarcat este setul de cuvinte de forma xy , unde x este un cuvânt de L și există un cuvânt de M .
Câtul la stânga a unui cuvânt este setul de cuvinte , cum ar fi aparține . Cocientul din stânga se mai numește și rezidual .
Câtul din dreapta al unui cuvânt este definit simetric ca set de cuvinte , cum ar fi aparține .
Coeficientul de pe stânga , iar coeficientul pe partea dreaptă extinde la limbi. Astfel, coeficientul din stânga unei limbi , notat , este unirea limbilor pentru în .
Kleene stea din L este setul observat compus din cuvinte de forma cu și . Acest set conține cuvântul gol .
Reversul de L , notat sau conține oglindă cuvintele cuvintele lui L , adică cuvintele lui L citit de la dreapta la stânga.
Amestecul de L și M , notat L Ш M este setul de cuvinte care pot fi scrise în cazul în care și sunt cuvinte (eventual gol) ca un cuvânt de L și un cuvânt de la M . De exemplu Ш .
O aplicație este un morfism sau omomorfismelor si pentru toate cuvintele de . Imaginea homomorphic unei limbi pe este setul
.Prin abuz de limbaj, numim morfism invers inversul unui morfism. Morfismul invers al este funcția notată a în ansamblul părților definite de
.În general nu este un morfism. Imaginea printr - un morfism inversă a unei limbi de pe este limba
.Un morfism nu se șterge sau crește sau, prin imitarea limbii engleze, este ε-free dacă imaginea unei litere nu este niciodată cuvântul gol. În acest caz, lungimea imaginii unui cuvânt este mai mare sau egală cu cea a cuvântului.
O întrebare comună cu privire la aceste operații este de a cunoaște proprietățile de închidere ale fiecărei familii de limbi pentru fiecare dintre aceste operații, adică dacă limba rezultată dintr-o operație rămâne în aceeași familie de limbi ca și limbile din care provine.
Limbi raționale |
Limbaje algebrice deterministe |
Limbaje algebrice |
Limbaje contextuale |
Limbaje recursive |
Limbi recursiv enumerabile |
|
---|---|---|---|---|---|---|
Uniune | Închis | Fără gard | Închis | Închis | Închis | Închis |
Intersecție | Închis | Fără gard | Fără gard | Închis | Închis | Închis |
Complementar | Închis | Închis | Fără gard | Închis | Închis | Fără gard |
Concatenare | Închis | Fără gard | Închis | Închis | Închis | Închis |
Steaua lui Kleene | Închis | Fără gard | Închis | Închis | Închis | Închis |
Oglindă | Închis | Fără gard | Închis | Închis | Închis | Închis |
Amestecat | Închis | Fără gard | Fără gard | Fără gard | Fără gard | Fără gard |
Morfism | Închis | Fără gard | Închis | Fără gard | Fără gard | Închis |
Morfism în creștere | Închis | Fără gard | Închis | Închis | Închis | Închis |
Morfism invers | Închis | Închis | Închis | Închis | Închis | Închis |