Limbaje formale

În matematică, logică și informatică, 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. Putem vorbi despre limbaje formale în multe contexte (științific, legal, lingvistic și altele) dar în acest articol vom trata limbajele formale în sensul de limbaj studiat de teoria limbajelor formale.

Familiarizare

Un exemplu de alfabet poate fi $\left \{ a , b \right \}$, și un șir peste acest alfabet ar putea fi $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 $a$ și $b$.

Cuvântul vid (adică șirul de lungime 0) este permis și este de obicei notat cu $e$, $\epsilon$ sau $\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ă lungimea cuvintelor din el poate fi nelimitată).

Exemple de limbaje

Câteva exemple de limbaje formale:

• mulțimea tuturor cuvintelor peste alfabetul ${a, b}$
• mulțimea $\left\{ a^{n}\right\}$, unde n număr prim și $a^{n}$ înseamnă $a$ repetat de $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ă $L_{1}$ și $L_{2}$ sunt două limbaje peste același alfabet.

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