Limbaje formale și automate

Prelucrarea informatiilor cu ajutorul calculatoarelor electronice

presupune lucrul cu siruri de caractere, de aceea este important de

studiat proprietatile si modurile de generare a sirurilor de caractere.

- In acest paragraf vom introduce not

iunile de baza

pentru limbaje for-

male si teoria automatelor.

Definitia 1.1.1. O multime finita si nevida V se numeste alfabet.

Elementele lui V se numesc simboluri sau simboli.

Definitia 1.1.2. Se numeste cuvant peste alfabetul V o aplicatie

p : {1, 2, , n} - V Numarul n se numeste lungimea cuvantului p

si se noteaza cu l(p) sau - p-

Cuvantul p se noteaza cu p(1)p(2) p(n). Multimea cuvintelor

peste alfabetul V se noteaza cu V +.

Exemplul 1.1.3. Fie V = {a, b, c, d} si cuvantul p : {1, 2, 3} - V

definit prin p(1) = a, p(2) = c, p(3) = d. Acest cuvant se scrie acd.

Fie u : {1, 2, 3, 4, 5} - V definit prin u(1) = b, u(2) = a, u(3) = c,

u(4) = d si u(5) = a. Acest cuvant se scrie bacda.

1

Pe multimea cuvintelor peste un alfabet se poate defini operatia

de concatenare.

Definitia 1.1.4. Fie p : {1, 2, , n} - V si

q : {1, 2, ,m} - V Atunci concatenarea cuvintelor p si q este

cuvantul p - q : {1, 2, , n + m} - V definit prin

p - q(j) =

(

p(j) daca i - j - n

q(j - n) daca n + 1 - j - n + m

Concatenarea cuvintelor p si q se noteaza cu p - q sau simplu pq.

Din definitie urmeaza ca pq = p(1) p(n)q(1) q(m).

Vom nota cu V - = V + - {- }, unde - este un element nou, - 6- V +

pentru care extindem operatia de concatenare - - p = p - - = p pentru

orice p - V + si - - - = - Vom defini l(- ) = 0. Cuvantul - se numeste

cuvant vid sau cuvant nul.

Observatia 1.1.5. Operatia de concatenare este o operatie aso-

ciativa, adica: (pq)r = p(qr) - p, q, r - V -

Observatia 1.1.6. (V - , - ) este monoid, se numeste monoidul liber

generat de V

Observatia 1.1.7. Aplicatia l : V - - N care asociaza unui

cuvant p - V - lungimea sa l(p) este un homomorfism, adica l(p- q) =

l(p) + l(q); lungimea unui cuvant p se mai noteaza si cu - p-

Semigrupul (V - , - ) se numeste monoidul liber peste alfabetul V De

asemenea vom identifica cuvintele de lungime unu cu simbolurile lui

V Vom nota cu - V - numarul simbolurilor alfabetului V

Lema 1.1.8. Numarul cuvintelor de lungime k peste alfabetul V

este egal cu - V - k.

Demonstratie. Fie n = - V - Numarul cuvintelor de lungime 1

este egal cu n; numarul cuvintelor de lungime 0 este 1. Presupunem

proprietatea adevarata pentru cuvinte de lungime cel mult k - 1 si o

demonstram pentru cuvinte de lungime k. Deci numarul cuvintelor de

2

lungime k - 1 este nk- 1. Cuvintele de lungime k le putem obtine din

cuvinte de lungime k - 1 adaugand la sfarsit un simbol din V Deci

din fiecare cuvant de lungime k - 1 obtinem n cuvinte de lungime k.

Deci numarul cuvintelor de lungime k este nk- 1 - n = nk.

Observatia 1.1.9. Multimea cuvintelor peste un alfabet V este

o multime numarabila, ca reuniune numarabila de multimi finite.

V - = {- } - -

-

k=1{p - p - V - , l(p) = k}.

Observatia 1.1.10. Monoidul (V - , - ) nu este comutativ.

De exemplu, daca luam V = {a, b} si cuvintele p = ab si q = bb,

avem p - q 6= q - p.

Toader Jucan - Limbaje formale s- i automate, Editura Matrix Rom, Bucures- ti,

1999, 162 p.

2. Toader Jucan, Satefan Andrei - Limbaje formale sai teoria automatelor.Teorie sai

practica, Editura Universitatyii "Al. I. Cuza", Iasyi, 2002, 327p.

3. Gheorghe Grigoras- - Limbaje formale s- i tehnici de compilare, Editura

Universitat- ii "Al. I. Cuza", Ias- i, 1985, 256p.

4. Virgil Cazanescu - Introducere in teoria limbajelor formale, Editura Academiei,

BucuresEti, 1983.