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)
Publicat de: Virgil Giurgiu
Puncte necesare: 0

Extras din curs

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

Autocad pentru începători

C1.1.CONCEPTUL DE CAD TERMINOLOGIE - COMPUTER AIDED ENGINEERING -CAE-vizeazăetapeledecercetare,inovaresiconcepţie; - COMPUTER AIDED DRAWING/...

Programare orientată pe obiect C++

1. INTRODUCERE ÎN C++ Exista limbaje concepute strict pe baza conceptelor programării orientate pe obiecte (POO), de exemplu Simula sau Smalltalk....

Inginerie Software

Fazele dezvoltării unui produs software 1 Ce este ingineria programării? 2. Fazele ingineriei programării 2.1. Faza de analiză 2.2. Faza de...

Limbaje de Asamblare

Introducere. Necesitatea programării în limbaje de asamblare Modalităţile de programare s-au schimbat imens de la inventarea calculatorului, în...

Rețele de Calculatoare

O reţea de calculatoare (computer network) este un ansamblu de calculatoare interconectate prin intermediul unui mediu de comunicaţie (cablu...

Algoritmi

ETAPELE REZOLVARII UNEI PROBLEME ALGORITMUL – reprezintă o succesiune finită şi ordonată de operaţii univoc determinate, efectuate mecanic, care...

Administrare rețele de calculatoare

ELEMENTELE COMPONENTE ALE UNUI SISTEM DE CALCUL Monitorul Este o periferica de iesire/intrare si este caracterizat prin: - Diagonala ecranului...

Bazele programării

Introducere Organizarea datelor - Proces complex care presupune identificarea, clasificarea si descrierea proprietatilor acestora, gruparea...

Te-ar putea interesa și

Sisteme de ecuații

INTRODUCERE Ca urmare a gradului înalt de abstracţie atins de matematică în secolul nostru, există o tendinţă în fiecare dintre noi de a căuta să...

Proiectarea și implementarea unui generator de analizoare sintactice bazate pe relații de precedentă

Analizorul sintactic este o componentă obligatorie pentru orice compilator. Pentru a obţine un product soft (program) trebuie să creăm un program...

Procesarea informației nestructurate

I. EXPRESII REGULATE 1. Introducere Ce este o expresie regulată- O expresie regulată, pe scurt denumită şi RegEx sau RegExp, este un şir de...

Sisteme Lindenmayer în Viața Artificială

Partea I – Consideratii teoretice (studiu bibliografic) Capitolul I – Introducere 1. TEORIA LIMBAJELOR FORMALE CLASICE Ca definiţie generală un...

Aplicație grafică - conquest

I. 1. Descrierea Programului Programul reprezinta o aplicatie a unit-ului graph, un joc simplu de strategie (gen TBS, daca ar fi sa-l incadram in...

Conceptele Fundamentale ale Limbajelor de Programare

INTRODUCERE Obiectul disciplinei: limbajele de programare Obiective: · Studiul conceptelor fundamentale care stau la baza proiectării...

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...

Ai nevoie de altceva?