Limbaje formale

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

Î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[modificare | modificare sursă]

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[modificare | modificare sursă]

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[modificare | modificare sursă]

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

Operații cu limbaje[modificare | modificare sursă]

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[modificare | modificare sursă]