Extras din laborator
1. Reprezentaţi automatul sub formă de graf.
2. Construiţi gramatica regulată echivalentă cu automatul dat.
3. Este sau nu automatul dat determinist? De ce?
4. Dacă automatul este nedeterminist, construiţi automatul finit determinist echivalent
Reprezentaţi AFD în formă de graf.
5. Inventaţi un şir peste vocabularul care nu va fi acceptat de către automat. Arătaţi acest lucru scriind secvenţa (secvenţele) de configuraţii respectivă.
6. Pentru automatul finit AF=(Q, , - , q0, F) construiţi 5 şiruri acceptate de automat. Lungimea şirurilor să nu fie mai mică decât n+2, unde n este numărul de stări din Q.
7. Pentru fiecare şir x scrieţi secvenţa de configuraţii pentru acceptarea şirului, adică (q0, x) — (qi1, x1) — (qi2, x2) — … — (qf, ), unde qf F.
8. Petru toate cele 5 şiruri obţinute construiţi aplicând lema de pompare descompunerea x=uvw.
AF = ( Q, ,- , q0, F )
Q = {q0, q1, q2, q3}
= {a, b }
F = {q3}
- (q0,a) ={q1}
- (q1,b) ={q2}
- (q2,b) ={q3}
- (q3,a) ={q1}
- (q2,b) ={q2}
- (q1,a) ={q1}
1) Reprezentăm automatul sub formă de graf:
2. Construim gramatica regulată echivalentă cu automatul dat:
- (q0, a) = {q1} 1. q0 → aq1
- (q1, b) = {q2} 2. q1 → bq2
- (q2, b) = {q3} 3. q2 → bq3
- (q3, a) = {q1} 4. q3 → aq1
- (q2, b) = {q2} 5. q2 → bq2
- (q1, a) = {q1} 6. q1 → aq1
7. q2 → b
3. Este sau nu automatul dat determinist? De ce?
Automatul dat este nedeterminist, deoarece din starea q2 prin b se poate trece în 2 stări diferite: q2 sau q3
- (q2,b) ={ q2},{q3}.
4. Dacă automatul este nedeterminist, construiţi automatul finit determinist echivalent
Reprezentaţi AFD în formă de graf.
Q a b
q0 q1 -
q1 q1 q2
q2 - q2q3
q2q3 q1 q2q3
Preview document
Conținut arhivă zip
- Limbaje Formale.docx
Alții au mai descărcat și
Obiective: 1. Crearea, redenumirea, utilizarea şi ştergerea foilor de calcul tabelar; 2. Definirea şi formatarea celulelor; 3. Definirea...
Trei reguli faţă de un sit 1. Respectarea strictă a standardelor internet. 2. Alegerea riguroasă a conţinutului paginilor web. 3. Asigurarea...
In Microsoft Visual Studio cream C++ MFC Project , cu un sindur document. Aici vom incerca sa interpretam cu ajutorul graficii 2D, grafica 3D...
Affine: Cifrul afin este un tip de cifru de substitutie monoalphabetica. în care fiecare literă într-un alfabet este mapat la echivalentul său...
CALCUL TABELAR. PROCESOARE DE TABELE. EXCEL Prezentare generală a calculului tabelar Procesoarele de calcul tabelar sau generatoarele de foi de...
Lucrarea 1 Evaluarea si masurarea timpului de executie al unui algoritm 1.Definitia unui tip de date abstract - TDA Un TDA este un model...
1. Care este diferenta intre un semnal continuu si un semnal continuu cuantificat? In functie de evolutia temporala semnalele se clasifica in...
Sa se scrie o functie care calculeaza cel mai mare divizor comun dintre 2 nr numere intregi nenule, utilizand algoritmul lui Euclid. /* CMMDC */...
Te-ar putea interesa și
#include <iostream.h> #include <conio.h> #include <string.h> #include "afd.h" #include "afdc.h" #define L 100 void main(){ clrscr(); AFD a;...
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ă....
Lucrarea practică № 1 1. Pentru gramatica formală G=(VN, VT, P, S) construiți 5 șiruri care aparțin limbajului L(G) generat de această gramatică....
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...
Scopul lucrării: - Construirea unei gramatici regulate; - De construit 11 producții și 5 cuvinte cu arborii lor de derivare pe baza gramaticii de...
1. Introducere in limbaje formale. Definitii 2. Operatii pe limbaje 3. Expresii regulate 1. Introducere in limbaje formale. Definitii....
Capitolul 1 Ierarhia lui Chomsky. Generari de limbaje 1.1 Introducere Termenul de gramatica a fost atribuit sistemelor generative din respect...
CAPITOLUL I EVOLUŢIA TEHNOLOGIILOR BAZELOR DE DATE Introducere Tehnologia bazelor de date, ca sitehnologia informaţiilor a evoluat de–a lungul...