Limbaje Formale și Compilatoare

Curs
7/10 (1 vot)
Domeniu: Calculatoare
Conține 1 fișier: doc
Pagini : 17 în total
Cuvinte : 4389
Mărime: 50.74KB (arhivat)
Cost: Gratis

Extras din document

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:

Preview document

Limbaje Formale și Compilatoare - Pagina 1
Limbaje Formale și Compilatoare - Pagina 2
Limbaje Formale și Compilatoare - Pagina 3
Limbaje Formale și Compilatoare - Pagina 4
Limbaje Formale și Compilatoare - Pagina 5
Limbaje Formale și Compilatoare - Pagina 6
Limbaje Formale și Compilatoare - Pagina 7
Limbaje Formale și Compilatoare - Pagina 8
Limbaje Formale și Compilatoare - Pagina 9
Limbaje Formale și Compilatoare - Pagina 10
Limbaje Formale și Compilatoare - Pagina 11
Limbaje Formale și Compilatoare - Pagina 12
Limbaje Formale și Compilatoare - Pagina 13
Limbaje Formale și Compilatoare - Pagina 14
Limbaje Formale și Compilatoare - Pagina 15
Limbaje Formale și Compilatoare - Pagina 16
Limbaje Formale și Compilatoare - Pagina 17

Conținut arhivă zip

  • Limbaje Formale si Compilatoare.doc

Alții au mai descărcat și

Limbaje Formale

1. Reprezentaţi automatul sub formă de graf. 2. Construiţi gramatica regulată echivalentă cu automatul dat. 3. Este sau nu automatul dat...

Limbaje formale și proiectarea compilatoarelor

Scopul lucrării: 1.Pentru gramatica formală G=(VN, VT, P, S) construiţi 5 şiruri care aparţin limbajului L(G) generat de această gramatică....

Limbaje Formale și Translatoare

1. Introducere Curs1 LFT Limbajele de nivel înalt au o serie de avantaje în raport cu limbajele de asamblare. Pentru a putea însă folosi limbaje...

Cursuri Baze de Date

1. Concepte Distinctia între date, informatii si cunostinte : - datele sunt definite de trei elemente: un identificator, atribute si valoare ; -...

Utilizare SQL

Utilizare SQL Prin natura suportului fizic, BDM sunt stocate ca fisiere bidimensionale tehnologia OLAP in varianta ROLAP are in vedere acest...

Webdesign

I. Consideraţii generale privind Internet şi World Wide Web La ora actuală în lume există milioane de calculatoare, care sunt folosite în cele mai...

Programarea Orientata spre Obiecte - Limbajul Java

1. INTRODUCERE IN PROGRAMAREA ORIENTATA SPRE OBIECTE OBIECTE D. Un obiect este un un mod simplificat de a identifica într-un program un lucru, o...

Solutia LINUX de Conectare la Internet

PARTEA INTAI - Conectarea unui LAN la Internet - Cazul clasic al conectarii la Internet Pentru ca un calculator sa fie conectat la Internet...

Ai nevoie de altceva?