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.

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$ . 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 $\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.

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_{1}$ şi $L_{2}$ sunt două limbaje peste acelaşi alfabet.

Concatenarea $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$ lui $L_{1}$ cu $L_{2}$ constă din toate şirurile conţinute în $L_1$ dar ş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}$ .
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}$ .
Kleene star $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 $n = 0$ 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.

Gourt Home::Gourt :: Limbaje formale