Limbaje Formale 3

3.4 Definiţie. Fie x, y, z ∈ A* şi w = xyz . x se numeşte prefix al lui w, y se numeşte

factor al lui w, iar z se numeşte sufix al lui w.

În cazul în care unul dintre x,y,z este diferit de cuvântul vid, ε , la denumirea dată

mai sus i se ataşează adjectivul „propriu” ( de exemplu, pentru x,îl vom numi prefix

propriu). Orice scriere a unui w∈ A* ca şi concatenare de tipul n w u u ...u 1 2 = , unde

u A* i ∈ , va fi numită factorizare a lui w.

Este clar că, dat un alfabet A, semigrupul liber pe A, A+ are foarte multe cuvinte

( Ν ) A însă nu orice cuvânt poate avea o semnificaţie în întelegerea noastră. Să

exemplificăm:

3.2 Exemple.

10 În aritmetica elementară se utilizeaza

alfabetul A ={0,1,2...,9}∪{+,−,⋅,:, =}∪ {(,)}.

Cuvântul (+ ⋅)9 , de exemplu, nu are nici o semnificaţie în aritmetică. Mai mult,

împărţirea prin 0 nu este definită, deci un cuvânt de forma 9:0=1 nu poate apărea în

aritmetică. În schimb, 1+3=4, este un cuvânt în aritmetică.

20 Fie A alfabetul constituit din toate cuvintele limbii române. Cuvintele, pe post

de simboluri, pot fi alăturate pentru a obţine, de exemplu, propoziţii, care vor fi cuvinte

peste A. Însa nu orice alăturare de simboluri dau cuvinte coerente în limba română:

(Studiem, limbaje, formale, şi, teoria, automatelor) are sens, în schimb (formale,

şi, limbaje, studiem, automatelor, teoria) ?!! ☺

Aceste exemple fac naturală urmatoarea:

3.5 Definiţie. Fie A un alfabet. Se numeşte limbaj peste A o submulţime L din P(A*).

3.3 Exemple.

10 Fie A alfabetul din exemplul 3.2, 10. Putem considera L ca fiind limbajul

tuturor adunărilor corecte din aritmetică. Aşadar cuvântul 11+13=24 este în limbaj, in

timp ce 9:3=3, chiar dacă este corect din p.d.v. aritmetic, nu se află în limbajul L.

20 In informatică, mulţimea tuturor programelor corecte din punct de vedere

sintactic într-un anumit limbaj, cum ar fi Java, constitue un limbaj.

În cele ce urmează, vom introduce diferite operaţii cu limbaje - adică moduri în

care putem „combina” limbajele pentru obţinerea unora noi.

Dupa cum s-a definit notiunea de limbaj, este clar ca multimea tuturor limbajelor

pe alfabetul A este Ρ(A*). Aşadar putem vorbi de aşa numitele „operaţii Booleene”,

adică intersecţia, reuniunea, şi complementarierea. Astfel, dacă L şi M sunt limbaje peste

acelaşi alfabet A, avem:

L ∪M ={w∈ A* w∈ L sau w∈M} - reuniunea

L ∩M ={w∈ A* w∈ L si w∈M} - intersecţia

cL = A* L ={w∈ A* w∉ L} - complementul lui L

Pe lângă cele definite mai sus, mai avem şi L M = {w∈ A* w∈ L si w∉M} diferenţa