Limbaje formale

De la Wikipedia, enciclopedia liberă

Î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.

Un exemplu de alfabet poate fi , ş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, ε sau λ. Dacă alfabetul este de lungime finită şi lungimea cuvintelor este finită, un limbaj poate avea un număr infinit de membri (pentru că lungimea cuvintelor din el poate fi nelimitată).

Câteva exemple de limbaje formale:

• mulţimea tuturor cuvintelor peste alfabetul a,b
• mulţimea , unde n număr prim şi aⁿ î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.

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 maşina 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.

Se pot realiza operaţii pe limbaje pentru a obţine alte limbaje din acestea. Să presupunem că L₁ şi L₂ sunt două limbaje peste acelaşi alfabet.

• Concatenarea L₁L₂ constă din toate şirurile de forma vw unde v este un şir din L₁ şi w este un şir din L₂.
• Intersecţia lui L₁ cu L₂ constă din toate şirurile conţinute în L₁ dar şi în L₂.
• Reuniunea a lui L₁ şi L₂ constă din toate şirurile conţinute în L₁ sau în L₂.
• Complementul limbajului L₁ constă din toate şirurile peste alfabet care nu sunt conţinute în L₁.
• Câtul la dreapta L₁ / L₂ al lui L₁ cu L₂ constă din toate şirurile v pentru care există un şir w în L₂ aşa încât vw este în L₁.
• Kleene star constă din toate şirurile de forma w₁w₂...w_n cu şirurile w_i din L₁ şi . Aceasta include şi şirul ε deoarece n = 0 este o valoare permisă.
• Inversul conţine versiunile în oglindă ale tuturor şirurilor din L₁.
• Amestecarea lui L₁ şi L₂ constă din şirurile de forma v₁w₁v₂w₂...v_nw_n unde şi v₁,...,v_n sunt şiruri pentru care concatenarea v₁...v_n este din L₁ şi w₁,...,w_n sunt şiruri pentru care w₁...w_n este din L₂.

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.