Extras din laborator
Definitia 1.1.1.
Un automat finit determinist (AFD) este un 5 uplu A=(Q,Sigma,delta,q_0,F)
unde:
Q este o multime nevida, finita, numita multimea starilor;
Sigma este o multime nevida, finita, numita alfabetul de intrare;
delta:Q x Sigma >Q este functia de tranzitie;
q_0 din Q este starea initiala;
F inclus in Q este multimea starilor finale.
Observatia 1.1.1.
Un automat finit nedeterminist (AFN) difera de (AFD) doar prin functia de
tranzitie delta:Q x Sigma >2^Q, adica dintr o stare exista mai multe
posibilitati de a trece in alta stare.
Exemplul 1.1.1.
Fie automatele date prin tabelele de tranzitie:
A_1=({q_1,q_2,q_3},{a,b},delta,q_1,{q_2,q_3})
Q Sigma | a b
q1 | q1 q2
q2 | q1 q3
q3 | q2 q1
A_2 = ({q_1,q_2,q_3},{a,b},delta,q_1,{q_2,q_3})
Q Sigma | a b
q1 | {q1,q2} {q2}
q2 | {q1,q3} {q3}
q3 | {q2,q3} {q1}
A_1 este un exemplu de AFD, iar A_2 un exemplu de AFN.
Definitia 1.1.2.
Dat A un (AFD), cu functia de tranzitie delta:Q x Sigma > Q, numim functia
de tranzitie extinsa delta`:Q x Sigma* > Q, functia definita astfel:
1. delta`(q,lambda)=q, oricare ar fi q din Q;
2. delta`(q,ua)=delta(delta`(q,u),a), oricare ar fi u din Sigma*,
oricare ar fi a din Sigma.
Pentru simplitatea notatiei, delta` se noteaza tot cu delta
(aceasta notatie este justificata si de faptul ca delta`(q,a)=delta(q,a),
oricare ar fi q din Q, oricare ar fi a din Sigma.
Conținut arhivă zip
- Tehnici de Compilare
- BIBL.TXT
- LAB_10.TXT
- LAB_11.TXT
- LAB_12.TXT
- LAB_13.TXT
- LAB_14.TXT
- LAB_1_2.TXT
- LAB_3.TXT
- LAB_4.TXT
- LAB_5.TXT
- LAB_6_7.TXT
- LAB_8_9.TXT
- PROGRAME.TXT
Alții au mai descărcat și
3.Introducere in bd si sgbd-uri Definitie: Numim baza de date o colectie partajata de date aflata in interdependenta logica impreuna cu o...
1 Introducere - organizarea unui compilator Un compilator este un program complex care realizează traducerea unui program sursă într-un program...
Te-ar putea interesa și
Introducere Lucrarea cuprinde metode tradiţionale de calcul matriceal care sunt utilizate frecvent în practică, metode reanalizate şi revăzute...
1. Sistemele expert si inteligenta artificiala Inteligenta artificiala este un domeniu care retine din ce în ce mai mult atentia economistilor,...
Istoricul Sistemului de Operare UNIX Unix-ul este un sistem de operare relativ vechi, fiind creat la Bell Laboratories în 1969, unde a fost...
Pentru a creste performanta procesoarelor a fost dezvoltata tehnica “benzii de asamblare”, numita si pipeline. Majoritatea procesoarelor din zilele...
Raspunsuri grile 181. Auditul statutar este activitatea realizata de cenzori potrivit dispozitiilor legale, pe baza mandatului acceptat si...
Cap. 1. SISTEME PIPELINE Tehnica pipeline reprezintă o metodă de îmbunătătire a performantelor unui procesor sau a unei unităti aritmetice....
Automate finite. Rolul lor în modelarea activităţilor din analiza lexicală[1] Un program de recunoastere pentru un limbaj este acel program care...