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

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