Limbaje Formale - Curs 1

1. Introducere in limbaje formale. Definitii

2. Operatii pe limbaje

3. Expresii regulate

1. Introducere in limbaje formale. Definitii.

Definitie:

Un SED este un sistem care evolueaza generând spontan evenimente si ca atare poate fi definit ca un generator în urmatorul mod:

unde

Q = Multimea finita de stari

S = multime finita de evenimente(simboluri)= alfabet

q0 = Starea initiala

d = Functia de tranzitie de stare, definita astfel

Definitie:

Un ALFABET este o multime finita de simboluri.

Caracteristica : dimensiunea

Definitie:

Un CUVÂNT este o secventa finita de simboluri ale aceluiasi alfabet.

Caracteristica : lungimea cuvântului notata astfel : | w |

(se foloseste la compararea traiectoriilor care conduc la aceeasi stare)

Definitie:

Un LIMBAJ este un ansamblu (multime) de cuvinte cu simboluri ale aceluiasi alfabet.

NOTATII SPECIALE:

Cuvântul vid : e (corespunde evenimentului nul)

Limbaj vid : f (nu contine nimic)

ATENTIE ! f ¹ { e }.

Limbajul generat de SED – descrie evolutia unui SED prin secvente de evenimente.

In functie de gradul de abstractizare al SED se pot reprezenta:

- limbaj logic

Exemplu:

Fie evenimentele generate in aceasta ordine de un SED : e1, e2, e3, e4,… e7

Atunci limbajul generat de SED este secventa e1e2e3e4… e7 (nu conteaza decat ordinea in timp fara a se mentiona momentele de aparitie a evenimentelor).

- limbaj logic si temporizat

In cazul in care pentru fiecare eveniment se specifica (se asociaza) momentul aparitiei sale atunci limbajul generat de SED ar fi:

(e1,t1) (e2,t2) (e3,t3) (e4,t4)… (e7,t7).

- limbaj stocastic

Informatia despre momentul aparitiei evenimentelor este reprezentata prin functii de distributie de probabilitate.

Exemplu:

S={a,b,g} – alfabet.

L1={e, a,abb}; |L1|=3

L2={ toate sirurile posibile de lungime 3 începând cu a }=

={abg,aba,aga,aab,aaa,abb,agg,agb,aag}; |L2|=9.

L3={toate sirurile posibile de lungime finita care încep cu a}; |L3|=¥.

Observatie!

Pentru construirea cuvintelor componente ale unui limbaj se foloseste operatia de concatenare a:

- simbolurilor, ab, ue=eu=u.

- sirurilor, s=tuv. t prefix, u=subsir, v=sufix.

Exemplu:

Fie un buffer de capacitate 1 reprezentat in figura de mai jos.

Se cere limbajul generat de evolutia acestui sistem pe baza evenimentelor specificate în figura.

Conform definitiei SED se identifica multimea starilor, alfabetul de evenimente si functia de tranzitie pentru sistemul prezentat.

Avem o singura variabila de stare pentru buffer care poate lua valorile {0,1} :

0 – buffer gol

1 – buffer plin.

Q= {0,1}