Sisteme Lindenmayer în Viața Artificială

Partea I – Consideratii teoretice (studiu bibliografic)

Capitolul I – Introducere

1. TEORIA LIMBAJELOR FORMALE CLASICE

Ca definiţie generală un limbaj formal descrie un sistem formal. Sistemul formal are ca intrări un set de axiome (adevăruri apriorice) şi pe baza unor reguli de compunere generează la ieşire teoreme. În literatura de ştiinţa calculatoarelor limbajele formale sunt asociate cu gramaticile formale. La fel ca orice alt sistem, o gramatică pleacă de la un set de simboluri de intrare(vocabularul), are un set de reguli de compunere şi generează la ieşire secvenţe (şiruri) de simboluri. Mulţimea acestor secvenţe de simboluri formează un anumit limbaj. În concepţia acestei licențe despre o gramatică, ea poate fi reprezentată grafic astfel:

Se observă uşor din figura de mai sus faptul că o gramatică este analogă unui sistem sau proces general care are intrări, logică de funcţionare şi generează ieşiri. Logica de funcţionare a unui proces oarecare poate fi modelată prin regulile de compunere ale gramaticilor. Pe scurt rolul unei gramatici este acea de a genera şiruri de simboluri aparţinând unui limbaj. Procesul de generare pleacă totdeauna de la un anumit simbol al vocabularului numit simbol de start.

1.1 Limbaje formale

Un limbaj in sens general este o colecţie (finita sau nu) de secvenţe finite formate cu elementele (simbolurile) unui vocabular finit. Semnificaţia elementelor vocabularului determină aria de aplicare a limbajului. Pot fi limbaje naturale(elementele sunt cuvinte), limbaje de programare (teoria compilatoarelor), limbaje ce descriu procese economice sau activităţi umane (vocabularul este constituit din codificări ale evenimentelor elementare), limbaje ce descriu procese biologice (sisteme Lindenmayer).

Cu toate ca vocabularul este finit limbajul poate fi infinit. Un limbaj infinit nu poate fi enumerat, el poate fi descris si manipulat prin reguli de formare a frazelor (şiruri de simboluri) sale. Aceste reguli sunt descrise prin limbaje formale care sunt gramaticile asociate limbajelor. Regulile din cadrul unei gramatici furnizează un mecanism de generare şi un criteriu de corectitudine a frazelor limbajului.

Definiţia formală a limbajului şi apoi a gramaticii este tratata in continuare.

Limbajul

Un alfabet sau vocabular V este un set finit de elemente. Aceste elemente se numesc simboluri. Daca V = { a1 , a2 , , an } este un vocabular atunci orice secvenţă de simboluri de forma x = a i1 a i2 a ir cu r≥1, aij  V, j=1,2, r este un cuvânt sau şir peste mulţimea V. Lungimea unui şir se notează cu | x | si este egală cu numărul de simboluri din şir, in cazul nostru | x | = r. Şirul vid se notează cu  şi nu conţine nici un simbol, ||=0

Mulţimea tuturor şirurilor peste alfabetul V se notează cu V* şi se obţine prin concatenarea repetată a simbolurilor şi şirurilor peste V. Operaţia de concatenare se defineşte pentru 2 şiruri x = ai1ai2 air şi y = bj1bj2 bjs ca fiind şirul xy = ai1ai2 airbi1bi2 bjs cu |xy|=|x|+|y|=r+s. Concatenarea de şiruri este o operaţie asociativă dar necomutativă peste V*, adică pentru orice x,y  V* : xy  V*. Concatenarea repetată ( iterată ) a unui şir x este descrisă prin exemplul următor:

dacă x=ab atunci x2=xx=abab=(ab)2, x3=(ab)3 =ababab, , xi+1=xxi, x0={ }

Conform acestor definiţii, închiderea tranzitivă şi reflexivă a mulţimii V in raport cu operaţia de concatenare este V*

Orice submulţime L  V* este un limbaj pe vocabularul V iar V* este limbajul universal peste V. Limbajul V* fără şiruri vide se notează cu V+ = V* - { }.

Exemple de limbaje peste alfabetul V={ a, b, c, } includ:

Exemplu 1.1

L = { a,b,c, } (1)

L = { anbk : n 1 şi k 1 } (2)

L = { anbnck : n 1 şi k 1} (3)

L = {anbnc n: n 1 } (4)

L = { x : x {a,b}+ şi |x|a=|x|b } (5)

unde cu |x|y se notează numărul de apariţii ale lui y în x.

Fie două şiruri x, y V* Dacă y=uxv , pentru u, v V* , atunci spunem că x este un subşir (subcuvânt) al lui y Dacă y=xv , v V* atunci x se numeşte prefix a lui y,iar dacă y=ux , u V* atunci x este sufix al lui y Pentru y V* se notează cu Sub(x) , Pref(x) , Suf(x) mulţimea subcuvintelor, prefixelor şi, respectiv sufixelor lui y

Dacă x = ai1ai2 air este un şir din V atunci imaginea în oglindă (mirror) a lui x notată cu mi(x) sau x-1 este mi(x)=x-1= air ai2ai1 şi are proprietăţile:

(x-1)-1=x, (x-1)i=(xi)-1 pentru orice i≥0