Limbaje Formale și Compilatoare

Pentru a modela hardware-ul unui calculator (a simula functionarea lui) se introduce notiunea de automat. Automatul primeste niste date de intrare, este caracterizat printr-un set de decizii care conduc la datele de iesire. Poate dispune sau nu de un spatiu temporar de stocare.

Limbajul formal reprezinta o abstractizare a caracteristicilor generale ale limbajelor de programare. Un limbaj formal este dat de un set de simboluri si o multime de reguli care arata modul in care simbolurile se pot combina pentru a forma asa numitele propozitii. Limbajul formal este alcatuit din toate string-urile ce se pot forma pe baza regulilor date.

I. Automate finite

I.1. Automate finite deterministe

Definitia 1.1: A = ( Q ,  ,  , q0 , F ) se numeste automat finit determinist, unde:

Q este o multime finita denumita multime de stari

 este multime de simbolurilor (alfabetul automatului)

: Q x   Q functie de tranzitie

q0  Q este starea initiala

F  Q este multimea starilor finale

Presupunem ca avem un sir de caractere ‘s’ (de intrare). Un automat determinist functioneaza in felul urmator:

1. Automatul se pozitioneaza la inceputul sirului ‘s’ (pe pozitia primului caracter) si intra in starea initiala q0. Se trece la pasul 2.

2. Daca nu s-a ajuns la sfarsitul sirului s, atunci se trece la pasul 3, altfel se trece la pasul 4.

3. Automatul citeste caracterul urmator ‘c’ din textul ‘s’. Fie qj  Q astfel incat (qi,c) = qj. Se trece din starea curenta qi  Q intr-o stare qj  Q si se reia pasul 2.

4. Daca starea curenta qi  Q este stare finala (qi  F), se spune ca automatul a acceptat sirul ‘s’, in caz contrar automatul nu recunoaste (nu accepta) sirul ‘s’.

Pentru automate se foloseste o reprezentare grafica printr-un graf orientat notat GA = (N, A) denumit graf de tranzitie, in care nodurile (multimea N) este data de starile automatului, iar arcele (multimea A) sunt date de tranzitiile automatului. Fiecare arc este etichetat cu simbolul prin care se trece din starea corespunzatoare nodului capat initial al arcului in starea corespunzatoare capatului final al arcului. Cu alte cuvinte, tranzitiei (qi,c) = qj ii corespunde in graful de tranzitie arcul (qi, qj) etichetat cu simbolul ‘c’.

Consideram spre exemplificare automatul finit A = (Q, , , q0, F), unde:

Q = {q0, q1, q2}

 = {a, b, c}

F = {q1}.

Functia de tranzitie este definita astfel:

(q0, a) = q1

(q0, b) = q2

(q0, c) = q0

(q1, a) = q2

(q1, b) = q1

(q1, c) = q0

(q2, a) = q0

(q2, b) = q2

(q2, c) = q2

Graful de tranzitie atasat automatului A este:

Se observa ca starea initiala q0 se recunoaste pe desen prin faptul ca nodul q0 este marcat cu o sageata care intra in el. De asemenea, nodurile finale sunt marcate prin cerculete duble.

Definitia 1.2: Limbajul acceptat de automatul determinist A = (Q, , , q0, F) se noteaza cu L(A), unde: