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.
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.