Limbaje formale

Limbajul formal reprezintă o generalizare a noțiunii de limbă cu care suntem obișnuiți din viața de zi cu zi.

Noțiuni de bază

Pentru început, ne putem imagina un limbaj formal ca o limbă obișnuită, de exemplu româna. Din ce este alcătuită o astfel de limbă? Din cuvinte, pe care le legăm apoi în propoziții. Propozițiile nu ne vor interesa, ne vor interesa doar cuvintele. Din ce sunt făcute cuvintele? Din literele alfabetului. Așadar, vom începe cu alfabetul.

Alfabetul este o mulțime nevidă oarecare. Elementele alfabetului se numesc simboluri. Dacă vorbim despre română, este alfabetul clasic românesc, cu litere mici și mari, plus variantele cu semne diacritice (ă, â, î, ș, ț). Dacă nu am vrea să descriem româna, ci, de exemplu, numerele, alfabetul ar conține toate cele zece cifre. Alfabetul se notează adesea cu simbolul Σ.

Prin cuvânt, numit și șir de caractere, înțelegem un șir finit de simboluri dintr-un alfabet Σ. Dacă avem, de exemplu, alfabetul Σ= {a,b,c,d,e,…, z}, atunci sunt cuvinte șirurile „salut” sau „dragon”, dar nu și „seară” (nu avem litera „ă”), „Ion” (nu avem litera „I”) sau „buna ziua” (nu avem spațiu). Prin lungimea cuvântului înțelegem numărul de simboluri din care este alcătuit cuvântul.

Concatenarea cuvintelor: dacă avem două cuvinte a = a₁a₂… a_n și b = b₁b₂… b_m, atunci prin concatenarea lor se obține cuvântul ab = a₁a₂… a_nb₁b₂… b_m. Exemplu: prin concatenarea cuvintelor „salut” și „dragon” se obține cuvântul „salutdragon”. Concatenarea se notează fie cu un cerculeț, adică a ∘ b, fie deloc, iar cuvintele se scriu pur și simplu unul după altul, fără un simbol special pentru concatenare.

Cuvântul vid se notează ε și este cuvântul care are lungimea zero. Dacă concatenăm cuvântul a = a₁… a_n cu cuvântul vid ε, obținem înapoi cuvântul a. Adică are loc a ∘ ε = a.

Închiderea alfabetului Σ este mulțimea tuturor cuvintelor pe care le putem forma cu alfabetul Σ, inclusiv cuvântul vid. Închiderea se notează Σ^∗. Pentru alfabetul binar Σ= {0, 1} avem

$${\mathrm{\Sigma }}^{\ast }=\{\epsilon ,0,1,00,01,10,11,000,001,\dots \}$$

Uneori folosim și închiderea pozitivă a alfabetului, care este din nou mulțimea tuturor cuvintelor pe care le putem forma cu alfabetul, cu excepția cuvântului vid. Închiderea pozitivă se notează Σ⁺ și are loc Σ⁺ = Σ^∗ ∖ {ε}.

Exemple de alfabete

• Să ne întoarcem la exemplul cu româna. Fiecare cuvânt românesc se găsește în închiderea alfabetului care conține literele mici și mari și variantele cu semne diacritice (plus, eventual, cratima „-”). Dacă adăugăm la acest alfabet spațiul și semnele de punctuație (virgulă, punct, semnul exclamării, semnul întrebării, …), prin închidere obținem toate propozițiile pe care le putem forma în limba română. Desigur, în această închidere se vor afla și propoziții de felul „sadflsf kasdf kagrjewițiăâșțăkr kf fkjbsjbgvbadfgsa!!!:??: ::!?:?:sdf”.

• Dacă alfabetul nostru conține toate cifrele Σ= {0, 1, …, 9}, atunci în închidere vor fi toate numerele naturale – și încă altele. Vor fi acolo și cuvinte care încep cu zero, de exemplu 00054, și, în plus, cuvântul vid, care desigur nu este un număr.

• Alfabetul trebuie să fie nevid, deci cel mai mic alfabet are cel puțin un simbol. De exemplu, pentru alfabetul Σ= {!} am obține închiderea Σ^∗ = {ε, !, !!, !!!, !!!!, …}, adică mulțimea de cuvinte în care, pentru fiecare n ∈ ℕ, există un cuvânt cu n semne de exclamare și nu există niciun alt cuvânt.

• Fie Σ= {qw,c}. Acesta este un alfabet foarte ciudat, pentru că are ca simbol cuvântul qw. Această notație nu se folosește de obicei, pentru că este confuză și neobișnuită, dar ne putem imagina că lipim literele „q” și „w” astfel încât să formeze un singur caracter. Atunci putem vedea „qw” ca pe un simbol. Dacă din acest simbol formăm cuvântul „qwcqw”, acesta ar avea lungimea trei – ar fi alcătuit din simbolurile „qw”, „c” și „qw”. Nu întâlnim prea des astfel de alfabete, dar există situații în care avem nevoie de simboluri alcătuite din mai multe simboluri.

Limbajul formal

Limbajul (formal) peste alfabetul Σ este orice submulțime a lui Σ^∗. Pentru un limbaj L peste alfabetul Σ avem deci L ⊆ Σ^∗. Exemple de limbaje:

• În partea anterioară am definit alfabetul cifrelor Σ= {0, 1, …, 9}. Închiderea este formată din toate cuvintele alcătuite doar din cifre. Dacă adăugăm regula că cuvântul nu are voie să înceapă cu zero (cu excepția cuvântului „0”) și nu are voie să fie vid, obținem mulțimea numerelor naturale ℕ (în România, mulțimea numerelor naturale conține și zero). Are loc relația ℕ ⊆ Σ^∗, deci ℕ este un limbaj peste alfabetul Σ.

• La mulțimea de cifre de mai sus putem adăuga și caracterul minus „-”, deci Σ= {0, 1, …, 9, −}. Închiderea este formată din toate cuvintele alcătuite din cifre sau din semnul minus. Asta înseamnă însă că în închidere se află și cuvinte precum „12-84-”, „1-5-8” sau „-”. Limbajul numerelor întregi ℤ îl obținem adăugând trei reguli:

  • Caracterul minus nu apare deloc în cuvânt sau apare la începutul cuvântului.
  • Prima cifră din cuvânt nu poate fi zero, cu excepția cuvântului „0”.
  • Fiecare cuvânt trebuie să conțină cel puțin o cifră.

  Această mulțime descrie mulțimea numerelor întregi și este o submulțime a lui Σ^∗ – este deci un limbaj peste alfabetul Σ.

• Fie Σ= {0, 1}. Închiderea este formată din toate cuvintele alcătuite din cifrele 0 și 1. Limbajul L peste acest alfabet îl putem defini, de exemplu, ca mulțimea tuturor cuvintelor care conțin exact trei cifre 1. Putem fi și mai creativi și putem spune că limbajul L este mulțimea tuturor cuvintelor care reprezintă un format valid de fișier docx (ceea ce iese din Word).

• Rămânem la alfabetul binar Σ= {0, 1}. Orice șir de caractere (caractere obișnuite, de pe tastatură) poate fi transformat în formă binară, adică în șiruri de 0 și 1, și apoi înapoi, de exemplu cu ajutorul tabelului ASCII (sau, mai precis – tabelul ASCII transformă caracterele în numere, iar numerele din baza zece se pot transforma în numere în baza doi). Putem astfel defini limbajul tuturor cuvintelor care corespund unei adrese de email valide și acesta va fi în continuare un limbaj peste alfabetul binar.

Concatenarea limbajelor: se pot concatena și limbaje. Definiția este asemănătoare cu cea a produsului cartezian al mulțimilor. Fie două limbaje L₁ și L₂. Prin concatenarea lor L₁ ∘ L₂ obținem un nou limbaj, definit astfel:

$$L_1\circ L_2=\{w_1\circ w_2|w_1\in L_1,w_2\in L_2\}$$

Adică luăm toate cuvintele din limbajul L₁ și le concatenăm cu toate cuvintele din limbajul L₂. Exemplu: fie

$$\begin{array}{rcl}{L}_1& =& \{0,1\}\\ L_2& =& \{a,b,salut\}\end{array}$$

Atunci are loc:

$$\begin{array}{rcl}{L}_1\circ L_2& =& \{0a,0b,0salut,1a,1b,1salut\}\\ L_2\circ L_1& =& \{a0,a1,b0,b1,salut0,salut1\}\\ L_1\circ L_1& =& \{00,01,10,11\}\end{array}$$

Până acum, pentru a descrie limbajele am folosit limba obișnuită, adică am descris în cuvinte cum trebuie să arate limbajul. Acest lucru este însă foarte nepractic, așa că se introduc modalități mai formale de a defini un limbaj. Prima dintre ele este gramatica.