LFA (si pentru IFR) - Curs din saptamana a 7-a [pg 47] -Ora a II-a

AUTOMATE FINITE

Deschideti manualul de Limbaje formale si teoria automatelor la pagina 47 (49 pe pdf).
Ati intrebat care curs se leaga cu care capitol de la practica ? Ei bine acest capitol face legatura cu capitolul al III-lea din manualul de constructia compilatoarelor. Da, grupele care sunt cu laboratorul acela terminat vor incepe sa inteleaga cum ajungem la acele expresii regulare din fisierul simple.y.
Ele sunt de fapt notatii pentru niste automate. Acele automate sunt reprezentabile usor ca niste grafuri, dar trebuiesc scrise in limbajul de programare al Flex-ului sau in alte limbaje de programare. Cum scrii un automat in limbaj de programare... vom vedea, ca o expresie regulara.

Dar stop, sa explicam ce sunt acestea...

Incepem sa citim paragraful 2.1 AFD si AFN.
Ce ati inteles din prima jumatate a paginii 47 ?
Sa rezumam si sa mai explicam cate ceva:

Iararhia lui Chomsky va indica existenta  unor gramatici foarte rapide la analiza sintactica, dele de tip 3. Ele au reguli atat de simple, de felul A->aB incat pot fi transformate in altfel de dispozitive, niste dispozitive cu stari care isi schimba starea (cam ca un caleidoscop care se roteste - comparatia e putin fortata) la fiecare citire a unui atom lexical din fluxul de intrare.

Dat fiind ca toate regulile unei astfel de gramatici sunt de forma A->aB (exceptie eventualele reguli A->a) rezulta ca o astfel de regula care se aplica la citirea literei a de la intrare ar pute duce sistemul dintr-o stare notata A intr-o stare notata B.

De aici ideea unui sistem care sare (cam ca o broasca care sare de pe o piatra pe alta) de la o stare la alta in momentul cand primeste un simbol terminal (un caracter) la intrare. Sa imi amintiti sa va spun povestea broastei montane !
Dupa ce parcurge TOT textul de la intrare, ceea ce inseamnan ca dupa cele n litere ale unu text ajunge in a n+1-a stare, daca aceasta e una dintre starile numit FINALE, cuvantul este acceptat, recunoscut, validat.

                 a
[A]  ------------------->  [B]
starea A            starea B

Automatele de acceptare sunt niste dispozitive pentru recunoasterea textelor (pentru analiza lexicala ar spune compilatoristul). Ele sunt finite, altfel  nu le-as putea implementa practic.

Pentru a le descrie avem doua modele (modelul fizic pg 47 [e-pdf pg49]) si modelul formal (pg 48, [e-pdf pg 50]) si o reprezentare - ati folosit-o la practica, expresia regulara.

a) modelul fizic
Imaginati-va automatul construit cam ca telegraful lui Samuel morse, insirat pe un sevalet, cu rola de banda pe care scrie si capul de scriere cu un electromagnet care perforeaza banda. Acum sa schimbam imaginea putin:
Imaginati-va un telegraf pe dos, cam ca un cititor de banda perforata de la computere, care are o rola de banda cu simboluri pe care le citeste un cap de citire. 
Sa mai schimbam imaginea un pic: Va amintiti acele unitati de banda magnetica din filmele SF vechi, cu calculatoare. O banda magnetica cu simboluri inregistrate trece prin fata unui cap - dar sa fie la noi numia pentru citire. Ceea ce citeste capultrece apoi la prelucrat la unitatea centrala, pe care sclipesc in film beculete, semn ca ea isi schimba starea.

Vedeti poza de la pagina 47.

Acum cititi la pg 48 paragraful despre functionarea automatului, cel putin cea informala. In esenta , daca UC ii permite, sistemul:
1) citeste un nou caracter de la intrare
deplaseaza capul de citire la urmatorul
2) trece intr-o noua stare
samd
pina termina sirul d ela intrare si ajunge intr-o stare, s-o notam f.

Va fi important sa retineti ca:
- textul ramas la intrare si starea in care ajunge formeaza o noua configurati, ele fiind puse impreuna (chiar vor fi intr-o paranteza).
- dupa terminarea textului se verifica in ce stare a ajuns automatul, nu inainte.

b)modelul formal, matematic [pg 48 la mijloc]
Ca sa simulam, ca sa notam, functionarea automatului fizic de mai sus vom folosi modelul matematic. (Orice chestie cu reguli precise de functionare e matematizabila, ba chiar si unele cu reguli mai putin precise.

Ora 17:

Definitia 2.1
In definitia automatului finit:
Q - e multimea de stari (pot fi orice, chiar si alte multimi de stari de la alt automat, v-am prevenit!)
Σ - este tot alfabelul de intrare, (simbolurile de pe sageti din diagrame)
δ : Q x Σ -> P(Q) este functie de la o stare din q si un simbol din alfabet la o stare sau mai bine la o multime de stari [P(Q) - inseamna "partile lui Q" - adica multimea submultimilor lui Q.
q0 - este starea initiala din care automatul pleaca, 0 e indice inferior de obicei dar o puteti nota si altfel.
F e submultime a lui Q - sunt starile finale, acelea in care daca automatul ajunge EXACT la sfarsitul secventei citite, TAMAN cand aceasta se termina, atunci intelegem ca textul este acceptat.

Cititi Observatia de la pagina 48 [pg 50 in e-pdf]
Nota noastra: de fapt putem defini cu definitia de mai sus doua feluri de automate:

AFD - Automat finit determinist, in care se poate sti exact in ce stare se ajunge, 
Cardinalul multimii |δ(q,a)|  mai mic sau egal cu 1. Aici se stie exact daca pt o stare si un simbol rezulta ori multimea vida (blocaj) sau exact o alta stare.

AFN -Automat finit nedeterminist, aici de la o stare si un simbol se ajunge la o multime potentiala de stari (cam ca la sistemele cuantice unde particula ajunge undeva intr-un spatiu dar nu stii unde, stii doar probabilitatile - la noi nu am probabilitati, doar potentialitatea). Automatul e un AFN daca macar intr-o situatie intr-o stare q:
|δ(q,a)| > 1 deci am, cumva, "mai multe stari finale simultan".


Va rog cititi observatiile de l pg 48.


Urmeaza sa definim cum se schimba configuratia (perechea aceeea stare-string de intrare) unui automat.
La fel ca la gramatici, vom defini mai multe relatii de tranzitie :
tranzitia directa
k-tranzitia
+tranzitia
*tranzitia

Gasiti definitiile lor la pg 49 [pg 51 pe e-book]. Vom relua de aici...

Final de curs ... trecem la ora de seminar/laborator.



Continuam ...