Technici Euristice

Curs
8/10 (1 vot)
Domeniu: Calculatoare
Conține 7 fișiere: pdf
Pagini : 58 în total
Cuvinte : 25273
Mărime: 866.62KB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Horia Ciocarlie
Automate finite. Rolul lor în modelarea activităţilor din analiza lexicală ANALIZA SINTACTICĂ ASCENDENTĂ Construirea tabelelor de analiză sintactică în varianta SLR

Extras din document

Automate finite.

Rolul lor în modelarea activităţilor din analiza lexicală[1]

Un program de recunoastere pentru un limbaj este acel program care primeste la

intrare un sir “X” si răspunde “DA” dacă “X” este o secvenţă a limbajului, respective“NU”, în

caz contrar. Pentru a analiza programul de recunoastere corespunzător unei expresii regulate

(program gen analizor lexical) trebuie contruită, în prealabil, o diagramă de tranziţii

generalizată numită automat finit (AF).

Un AF poate fi determinist (AFD) sau nedeterminist (AFN). Nedeterminarea constă,

în principiu, în faptul că, din cel puţin o stare sunt posibile mai multe tranziţii pentru acelasi

simbol de intrare.

Atât AFD cât si AFN pot recunoaste limbaje specificate prin expresii regulate. De

obicei AFD conduc la programe mai rapide dar numărul lor de stări este mai mare.

Există metode de transformare (conversie) a expresiilor regulate în ambele tipuri de

automate. Conversia este mai simplă în cazul AFN.

În exemplele ce urmează în acest paragraf se va utiliza următoarea expresie

regulată[1]:

(a|b)*abb – mulţimea tuturor sirurilor compuse din caractere a si b care se termină

cu secvenţa abb (ex: abb, aabb, babb, aaabb, )

1.1 Definiţia unui AFN

Un AFN este un model matematic reprezentat prin următorul cvintet:

AFN = <S,A,ft,so,F>, unde:

- S este mulţimea stărilor;

- A reprezintă mulţimea simbolurilor de intrare (alfabetul de intrare);

- ft se numeste funcţie de tranziţie si pune în corespondenţă perechi „staresimbol”

cu ”stări”, adică: ft : S x A -> S ;

- so este starea iniţială (de start); soÎS;

- F este mulţimea stărilor finale (acceptoare); F Í S.

Un AFN se poate reprezenta ca un graf orientat etichetat numit graf de tranziţie în

care nodurile corespund stărilor automatului iar etichetele descriu funcţia de transfer (ft). Se

poate remarca asemănarea dintre un graf de tranziţie si o diagramă de tranziţie. Deosebirile

de principiu sunt următoarele:

- acelasi caracter se poate utiliza pentru a eticheta două sau mai multe tranziţii din

aceasi stare;

- este permisă utilizarea ca etichetă a simbolului ε (sirul vid).

În fig. 1.1 se prezintă un exemplu de AFN corespunzător expresiei regulate:

(a|b)*abb. Nedeterminismul se manifestă în starea 0 în care, pentru simbolul de intrare a,

sunt posibile 2 tranziţii: se poate rămâne în starea 0 sau se poate trece în starea 1.

Fig. 1.1 Un prim exemplu de AFN pentru expresia: (a|b)*abb

În calculator, funcţia de tranziţie se poate implementa în mai multe moduri. O

modalitate potrivită este sub forma unei tabele de tranziţii care au câte o linie pentru fiecare

stare, câte o coloană pentru fiecare simbol de intrare (inclusiv pentru simbolul ε, daca este

necesar) (fig. 1.2). Intrarea în tabelă corespunzătoare liniei i si simbolului de intrare a este

mulţimea de stări pentru care există tranziţii din starea i etichetate cu simbolul a.

Stare Simbol intrare

a b

0 {0,1} {0}

1 - {2}

2 - {3}

3 - -

Fig 1.2 Tabela de tranziţii corespunzătoare AFN din fig. 1.1

Se spune că un AFN acceptă un sir de intrare ”X” dacă si numai dacă există un drum

în graful de tranziţii începând din starea de start până la o stare acceptoare astfel încât

etichetele pe drumul respectiv să formeze sirul ”X”. Drumul respectiv se numeste cale de

acceptare pentru sirul ”X”. Aceluiasi sir de intrare îi pot corespunde mai multe căi de

acceptare într-un AFN. Totalitatea sirurilor acceptate de un AFN reprezintă limbajul definit

de automatul respectiv.

1.2 Definiţia unui AFD

Un AFD este un caz particular de AFN la care se impun următoarele restricţii asupra

funcţiei de transfer ft.

1) din nici o stare nu pleacă tranziţii etichetate cu ε;

2) pentru orice stare s si pentru orice simbol de intrare a, există cel mult un arc etichetat

cu a care pleacă din s.

În concluzie, un AFD va avea cel mult o tranziţie din fiecare stare pentru orice simbol de

intrare. Aceasta înseamnă ca AFD conţine cel mult o cale de acceptare (recunoastere) pentru

un sir de intrare dat.

În fig. 1.3 se prezintă

Preview document

Technici Euristice - Pagina 1
Technici Euristice - Pagina 2
Technici Euristice - Pagina 3
Technici Euristice - Pagina 4
Technici Euristice - Pagina 5
Technici Euristice - Pagina 6
Technici Euristice - Pagina 7
Technici Euristice - Pagina 8
Technici Euristice - Pagina 9
Technici Euristice - Pagina 10
Technici Euristice - Pagina 11
Technici Euristice - Pagina 12
Technici Euristice - Pagina 13
Technici Euristice - Pagina 14
Technici Euristice - Pagina 15
Technici Euristice - Pagina 16
Technici Euristice - Pagina 17
Technici Euristice - Pagina 18
Technici Euristice - Pagina 19
Technici Euristice - Pagina 20
Technici Euristice - Pagina 21
Technici Euristice - Pagina 22
Technici Euristice - Pagina 23
Technici Euristice - Pagina 24
Technici Euristice - Pagina 25
Technici Euristice - Pagina 26
Technici Euristice - Pagina 27
Technici Euristice - Pagina 28
Technici Euristice - Pagina 29
Technici Euristice - Pagina 30
Technici Euristice - Pagina 31
Technici Euristice - Pagina 32
Technici Euristice - Pagina 33
Technici Euristice - Pagina 34
Technici Euristice - Pagina 35
Technici Euristice - Pagina 36
Technici Euristice - Pagina 37
Technici Euristice - Pagina 38
Technici Euristice - Pagina 39
Technici Euristice - Pagina 40
Technici Euristice - Pagina 41
Technici Euristice - Pagina 42
Technici Euristice - Pagina 43
Technici Euristice - Pagina 44
Technici Euristice - Pagina 45
Technici Euristice - Pagina 46
Technici Euristice - Pagina 47
Technici Euristice - Pagina 48
Technici Euristice - Pagina 49
Technici Euristice - Pagina 50
Technici Euristice - Pagina 51
Technici Euristice - Pagina 52
Technici Euristice - Pagina 53
Technici Euristice - Pagina 54
Technici Euristice - Pagina 55
Technici Euristice - Pagina 56
Technici Euristice - Pagina 57
Technici Euristice - Pagina 58

Conținut arhivă zip

  • Technici Euristice
    • Bibliografie.pdf
    • Cap. 1.pdf
    • Cap. 2.pdf
    • Cap. 3.pdf
    • Cap. 4.pdf
    • Cap. 5 folie 1.pdf
    • Cap. 5 folie 2.pdf

Alții au mai descărcat și

Proiect Java - Joc Carti - Macao

ENUNT: Folosind Java Swing, sa se proiecteze o aplicatie ce va simula un joc de carti (la alegere). Va fi disponibil un pachet de carti de joc,...

Prelucrarea Imaginilor Digitale 1

Esantionarea si cuantificare sunt realizate de dispozitivele de achizitie a imaginilor. Acestea pot consta intr-un singur senzor care se misca...

Colectii de Obiecte

C8 Colecţii ArrayList de obiecte definite de utilizator 1) Ce este o colecţie de obiecte? -o variabilă de memorie ce conţine o mulţime (o listă)...

Prelucrarea Imaginilor Digitale 2

Orice functie periodica poate fi exprimata ca o suma de functii cos si sin, fiecare multiplicata cu un coeficient: Seria Fourier O functie...

Sisteme Intrare Iesire

Cap. I – Introducere Structura generală a unui calculator personal compatibil IBM PC este prezentată în figura 1.1. 1. Microprocesorul este cel...

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

Sisteme de Operare

1.1 Sisteme de calcul. Structura sistemelor de calcul Sistemele de operare sunt colecţii de programe existente pe sistemele de calcul . Prin...

Algoritmi de Simulare

I.1 Analiza proceselor prin metoda elementului finit I.1.1 Tipuri de probleme Sub aspectul continuităţii: Statice Dinamice • Deşi pot fi...

Ai nevoie de altceva?