Limbaj formal

În matematică, logică, informatică și lingvistică un limbaj formal este o mulțime de cuvinte de lungime finită (șiruri de caractere) bazate pe un alfabet finit, și teoria științifică ce tratează aceste entități se numește teoria limbajelor formale. Se poate vorbi despre limbaje formale în multe contexte (științific, lingvistic, juridic, medical și altele) dar în acest articol tratează limbajele formale în sensul de limbaj studiat de teoria limbajelor formale.

Familiarizare

Un exemplu de alfabet poate fi ${\displaystyle \left\{a,b\right\}}$, și un șir peste acest alfabet ar putea fi ${\displaystyle ababba}$.

Un exemplu de limbaj peste acel alfabet și care conține șirul dat ca exemplu ar fi mulțimea tuturor șirurilor care conțin același număr de simboluri ${\displaystyle a}$ și ${\displaystyle b}$.

Cuvântul vid (adică șirul de lungime 0) este permis și este de obicei notat cu ${\displaystyle e}$, ${\displaystyle \epsilon }$ sau ${\displaystyle \lambda }$.

Chiar dacă alfabetul este de lungime finită și lungimea oricărui cuvânt este finită, un limbaj poate avea un număr infinit de membri (pentru că mulțimea cuvintelor din el nu e limitată).

Exemple de limbaje

Câteva exemple de limbaje formale:

• mulțimea tuturor cuvintelor peste alfabetul ${\displaystyle {a,b}}$
• mulțimea ${\displaystyle \left\{a^{n}\right\}}$, unde n număr prim și ${\displaystyle a^{n}}$ înseamnă ${\displaystyle a}$ repetat de ${\displaystyle n}$ ori
• mulțimea programelor corecte din punct de vedere sintactic într-un limbaj de programare
• mulțimea intrărilor pentru care o mașină Turing se oprește.

Modalități de construcție

Un limbaj formal poate fi specificat în mai multe feluri:

• Ca șiruri produse de o anumită gramatică formală (vezi ierarhia Chomsky);
• Șiruri produse de o expresie regulată;
• Șiruri acceptate de un automat, cum ar fi o mașină Turing sau un automat finit;
• Dintr-o mulțime de întrebări de tip DA/NU, cele al căror răspuns este da - vezi problema deciziei.

Operații cu limbaje

Se pot realiza operații pe limbaje pentru a obține alte limbaje din acestea. Să presupunem că ${\displaystyle L_{1}}$ și ${\displaystyle L_{2}}$ sunt două limbaje peste același alfabet.

• Concatenarea ${\displaystyle L_{1}\cdot L_{2}}$ (sau ${\displaystyle L_{1}L_{2}}$) constă din toate șirurile de forma ${\displaystyle vw}$ unde ${\displaystyle v}$ este un șir din ${\displaystyle L_{1}}$ și ${\displaystyle w}$ este un șir din ${\displaystyle L_{2}}$.
• Intersecția ${\displaystyle L_{1}\cap L_{2}}$ a lui ${\displaystyle L_{1}}$ cu ${\displaystyle L_{2}}$ constă din toate șirurile conținute atât în ${\displaystyle L_{1}}$ cât și în ${\displaystyle L_{2}}$.
• Reuniunea ${\displaystyle L_{1}\cup L_{2}}$ a lui ${\displaystyle L_{1}}$ și ${\displaystyle L_{2}}$ constă din toate șirurile conținute în ${\displaystyle L_{1}}$ sau în ${\displaystyle L_{2}}$.
• Complementul limbajului ${\displaystyle L_{1}}$ constă din toate șirurile peste alfabet care nu sunt conținute în ${\displaystyle L_{1}}$.
• Diferența ${\displaystyle L_{1}\setminus L_{2}}$ a lui ${\displaystyle L_{1}}$ și ${\displaystyle L_{2}}$ constă din toate șirurile conținute în ${\displaystyle L_{1}}$ dar nu și în ${\displaystyle L_{2}}$.
• Câtul la dreapta ${\displaystyle L_{1}/L_{2}}$ al lui ${\displaystyle L_{1}}$ cu ${\displaystyle L_{2}}$ constă din toate șirurile ${\displaystyle v}$ pentru care există un șir ${\displaystyle w}$ în ${\displaystyle L_{2}}$ așa încât ${\displaystyle vw}$ este în ${\displaystyle L_{1}}$.
• Închiderea Kleene ${\displaystyle L_{1}^{*}}$ constă din toate șirurile de forma ${\displaystyle w_{1}w_{2}...w_{n}}$ cu șirurile ${\displaystyle w_{i}}$ din ${\displaystyle L_{1}}$ și ${\displaystyle n\geq 0}$. Aceasta include și șirul ${\displaystyle \epsilon }$ deoarece acesta se obține pentru ${\displaystyle n=0}$, care este o valoare permisă.
• Inversul ${\displaystyle L_{1}^{R}}$ conține versiunile în oglindă ale tuturor șirurilor din ${\displaystyle L_{1}}$.
• Amestecarea lui ${\displaystyle L_{1}}$ și ${\displaystyle L_{2}}$ constă din șirurile de forma ${\displaystyle v_{1}w_{1}v_{2}w_{2}...v_{n}w_{n}}$ unde ${\displaystyle n\geq 1}$ și ${\displaystyle v_{1},...,v_{n}}$ sunt șiruri pentru care concatenarea ${\displaystyle v_{1}...v_{n}}$ este din ${\displaystyle L_{1}}$ și ${\displaystyle w_{1},...,w_{n}}$ sunt șiruri pentru care ${\displaystyle w_{1}...w_{n}}$ este din ${\displaystyle L_{2}}$.

O întrebare importantă pentru teoria limbajelor formale este "cât este de dificil să decidem dacă un cuvânt dat aparține unui limbaj?" Acesta este domeniul teoriei computabilității și teoriei complexității.

Legături externe

• University of Maryland, Formal Language Definitions
• James Power, "Notes on Formal Language Theory and Parsing" Arhivat în 21 noiembrie 2007, la Wayback Machine., 29 November 2002.

• Drafts of some chapters in the "Handbook of Formal Language Theory", Vol. 1-3, G. Rozenberg and A. Salomaa (eds.), Springer Verlag, (1997):t
  • Alexandru Mateescu and Arto Salomaa, "Preface" in Vol.1, pp. v-viii, and "Formal Languages: An Introduction and a Synopsis", Chapter 1 in Vol. 1, pp.1-39
  • Sheng Yu, "Regular Languages", Chapter 2 in Vol. 1
  • Jean-Michel Autebert, Jean Berstel, Luc Boasson, "Context-Free Languages and Push-Down Automata", Chapter 3 in Vol. 1 Arhivat în 27 martie 2008, la Wayback Machine.
  • Christian Choffrut and Juhani Karhumäki, "Combinatorics of Words", Chapter 6 in Vol. 1
  • Tero Harju and Juhani Karhumäki, "Morphisms", Chapter 7 in Vol. 1, pp. 439 - 510
  • Jean-Eric Pin, "Syntactic semigroups", Chapter 10 in Vol. 1, pp. 679-746
  • M. Crochemore and C. Hancart, "Automata for matching patterns", Chapter 9 in Vol. 2
  • Dora Giammarresi, Antonio Restivo, "Two-dimensional Languages", Chapter 4 in Vol. 3, pp. 215 - 267