Limbaj formal

(Redirecționat de la 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.

FamiliarizareModificare

Un exemplu de alfabet poate fi  , și un șir peste acest alfabet ar putea fi  .

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   și  .

Cuvântul vid (adică șirul de lungime 0) este permis și este de obicei notat cu  ,   sau  .

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 limbajeModificare

Câteva exemple de limbaje formale:

  • mulțimea tuturor cuvintelor peste alfabetul  
  • mulțimea  , unde n număr prim și   înseamnă   repetat de   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țieModificare

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

Operații cu limbajeModificare

Se pot realiza operații pe limbaje pentru a obține alte limbaje din acestea. Să presupunem că   și   sunt două limbaje peste același alfabet.

  • Concatenarea   (sau  ) constă din toate șirurile de forma   unde   este un șir din   și   este un șir din  .
  • Intersecția   a lui   cu   constă din toate șirurile conținute atât în   cât și în  .
  • Reuniunea   a lui   și   constă din toate șirurile conținute în   sau în  .
  • Complementul limbajului   constă din toate șirurile peste alfabet care nu sunt conținute în  .
  • Diferența   a lui   și   constă din toate șirurile conținute în   dar nu și în  .
  • Câtul la dreapta   al lui   cu   constă din toate șirurile   pentru care există un șir   în   așa încât   este în  .
  • Închiderea Kleene   constă din toate șirurile de forma   cu șirurile   din   și  . Aceasta include și șirul   deoarece acesta se obține pentru  , care este o valoare permisă.
  • Inversul   conține versiunile în oglindă ale tuturor șirurilor din  .
  • Amestecarea lui   și   constă din șirurile de forma   unde   și   sunt șiruri pentru care concatenarea   este din   și   sunt șiruri pentru care   este din  .

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 externeModificare