Limbaje formale

Limbaje formale

Introducere in limbaje formale. Definitii

Operatii pe limbaje

Expresii regulate

Introducere in limbaje formale. Definitii.

Definitie:

Un SED este un sistem care evolueaza generand spontan evenimente si ca atare poate fi definit ca un generator in urmatorul mod:

unde

Q = Multimea finita de stari

S multime finita de evenimente(simboluri)= alfabet

q₀ = Starea initiala

d = Functia de tranzitie de stare, definita astfel

Definitie:

Un ALFABET este o multime finita de simboluri.

Caracteristica : dimensiunea

Definitie:

Un CUVANT este o secventa finita de simboluri ale aceluiasi alfabet.

Caracteristica : lungimea cuvantului 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:

Cuvantul vid : e (corespunde evenimentului nul)

Limbaj vid : f (nu contine nimic)

ATENTIE ! f

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 : e₁, e₂, e₃, e₄, . e₇

Atunci limbajul generat de SED este secventa e₁e₂e₃e₄ . e₇ (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:

(e₁,t₁) (e₂,t₂) (e₃,t₃) (e₄,t₄) . (e₇,t₇).

limbaj stocastic

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

Exemplu:

S= - alfabet.

L₁=; |L1|=3

L₂==

=; |L₂|=9.

L₃=; |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 in 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 :

- buffer gol

- buffer plin.

Q

Evenimentele pe care le recunoaste sistemul sunt:

-- "intrare element" (a)

-- "iesire element" (b)

S

In acest context consideram starea initiala q₀ : (s=0) si functia de tranzitie va fi:

d(0,a) = 1

d(1,b) = 0

L = este limbajul generat de catre sistem.

Acest limbaj nu poate contine de exemplu cuvantul 'bab' pentru ca acesta nu corespunde unei evolutii posibile a sistemului (starea initiala fiind 0, dintr-un buffer gol nu poate iesi nici o piesa)

Observatie Presupunem ca stabilim o stare in care dorim sa ajunga sistemul. Acest tip de stari se numesc stari dorite sau stari marcate sau stari finale (ceea ce NU inseamna ca odata ajuns in acesta stare sistemul ramane intotdeauna in ea).

Definitie:

Limbajul marcat (L_m)este totalitatea evolutiilor care conduc intr-o stare dorita.

Un SED este complet descris de perechea (L,L_m) ;

L - limbajul generat de SED(toate evolutiile posibile);

L_m limbajul marcat (dorit/final) cu toate evolutiile dorite!

Pentru acest exemplu consideram starea dorita a sistemului nostru s=0 (buffer gol).

Limbajul marcat este:

L_m = (deci trebuie sa se termine in "b").

Proprietate: L_m L pentru un SED corect definit.

Operatii pe limbaje

Fie L₁, L₂ limbaje definite pe S - un alfabet oarecare.

S* - toate cuvintele formate cu simboluri din S

S ; L₁, L₂ S e S

1.Reuniune (Choice) L = L1 L2 =

2.Concatenare L = L1 L2 =

3.Inchidere iterativa (sau operatorul Kleene)

L = L*

Observatie! (L*)* = L*.

4.Inchidere iterativa stricta L = L⁺

Observatie! Inchiderea iterativa contine cuvinte infinite.

Observatie! Cuvantul nul apartine lui L⁺ daca si numai daca ε L (ε L* indiferent de aceasta conditie).

5.Inchidere prefixata a unui limbaj

pr(L) = L =     - toate prefixele tuturor sirurilor din L.

Proprietate : Limbajul generat de un SED este intotdeauna propria sa inchidere prefixata   pr(L)=L .

(Lucreaza ca un criteriu de verificare. Daca nu e indeplinit atunci nu e un limbaj generat.)

Explicatia fizica este :

Orice cuvant generat de SED inseamna o traiectorie de stare.

Pentru a atinge un punct dat, trebuie atinse punctele preliminare.

ababababababababa

pozitia vizata

Trebuie sa parcurg pe rand pozitiile anterioare(prefixate) pozitiei vizate.

Daca am avea perechea limbajelor (L, L_m ):

L =

L_m =,

In acest caz L L deoarece nu contine cuvantul a si atunci (L, L_m ) nu e un model corect pentru un SED si deci, nu se poate reprezenta!!!

Pentru exemplul cu bufferul: L=pr(L_m).

5.Proiectiile unui limbaj pe un alfabet S

Daca S S atunci L S

s I S T s S^ =   

) s I S s I S T ss S^ =

Exemplu:

Se da S =;

L₁ = ;

L₂ =

Atunci:

pr(L₁)=

(elementul nul, toate prefixele pentru fiecare cuvant si fiecare cuvant in parte).

L₂=

L₂ L₁ =

L₂* = .

3. Expresii Regulate

Expresiile regulate permit exprimarea mai compacta a limbajelor.

Nu toate limbajele pot fi modelate ca expresii regulate.

Definitie: Fie S un alfabet, atunci o expresie regulata(ER) se defineste astfel:

e este o expresie regulata care modeleaza limbajul ce contine doar evenimentul nul

f este o ER care modeleaza limbajul vid

) a I S , a este o ER care modeleaza limbajul reprezentat de

daca a, b sunt ER, atunci (a, b), (a+b), a*, b* sunt ER

(E,+, ) = algebra

Proprietate (foarte importanta): Daca a = ER, atunci : a e aa*

Demonstratie:

a a aa aaa + . = ε + a a aa aaa aa

Observatie! Pentru ca un SED sa poata fi reprezentat ca un automat finit trebuie ca limbajele generat (si respectiv cel marcat) sa poata fi reprezentate ca expresii regulate.

Exemplu:

Fie S=. Se cere expresia regulata care descrie limbajul format din cuvinte ce contin doua zerouri consecutive.

Limbajul care contine toate cuvintele ce se formeaza cu 0 si 1 este

L=

(0+1)(0+1)(0+1) T (0+1)* - toate combinatiile (cuvintele) care se formeaza cu 0 si 1.

Deci expresia regulata pentru acest L este : (0+1)*.

Limbajul cerut contine toate cuvintele care incep cu oricati de 0 si/sau oricati de 1, urmate de 2 zerouri si se termina in oricati de 0 si/sau oricati de 1.

Atunci (0+1)* 00 (0+1)* reprezinta:

toate cuvintele care pot fi construite pe S (0 si/sau1)

toate cuvintele care pot fi construite peste S si au doua simboluri zero consecutive.

Adica de exemplu avem:

0

1111

10