Scribd
Încărcați
4 vizualizări3 pagini

Gramatica-Automate 2023

Documentul detaliază cerințele pentru construirea unei aplicații care transformă o gramatică generativă regulată într-un automat finit. Se solicită definirea a două clase, Grammar și FiniteAutomaton, fiecare având metode specifice pentru verificarea validității, generarea cuvintelor și afișarea elementelor. De asemenea, se menționează implementarea unei funcții care să returneze un automat echivalent cu gramatică și un meniu interactiv pentru utilizator.

Încărcat de

Cezar Constandoiu
Drepturi de autor
© All Rights Reserved
Respectăm cu strictețe drepturile privind conținutul. Dacă suspectați că acesta este conținutul dumneavoastră, reclamați-l aici.
Formate disponibile
Descărcați ca PDF, TXT sau citiți online pe Scribd
4 vizualizări3 pagini

Gramatica-Automate 2023

Documentul detaliază cerințele pentru construirea unei aplicații care transformă o gramatică generativă regulată într-un automat finit. Se solicită definirea a două clase, Grammar și FiniteAutomaton, fiecare având metode specifice pentru verificarea validității, generarea cuvintelor și afișarea elementelor. De asemenea, se menționează implementarea unei funcții care să returneze un automat echivalent cu gramatică și un meniu interactiv pentru utilizator.

Încărcat de

Cezar Constandoiu
Drepturi de autor
© All Rights Reserved
Respectăm cu strictețe drepturile privind conținutul. Dacă suspectați că acesta este conținutul dumneavoastră, reclamați-l aici.
Formate disponibile
Descărcați ca PDF, TXT sau citiți online pe Scribd

(Categ1) Construirea unui automat nit

pentru o gramatic regulat

Enunµ

S se scrie o aplicaµie care pentru o gramatic generativ regulat G = (VN , VT , S, P )


construie³te un automat nit M = (Q, Σ, δ, q0 , F ), pentru care T (M ) = L(G).

Cerinµe

I. Se cere denirea unei clase Grammar (alta decât clasa principal - aviz celor
care programeaz Java sau C#!).
Membrii clasei vor : VN , VT , S, P - pentru mulµimea de producµii se poate
utiliza o clas /structur .

Metodele clasei - obligatorii. (Pot exista ³i altele, dac este necesar)

1. VerifyGrammar - veric dac gramatica citit este o gramatic corect /valid .


Aici trebuie s identicaµi din teorie, care sunt veric rile necesare.
2. IsRegular - veric dac gramatica este regulat sau nu.
3. GenerateWord() - genereaz un cuvânt pornind de la simbolul de start.
La generarea unui cuvânt în gramatic , producµia care se aplic la mo-
mentul curent trebuie aleas random dintre producµiile aplicabile la mo-
mentul curent. Se vor a³a toate combinaµiile prin care s-a trecut pân
la generarea cuvântului.
4. PrintGrammar() - a³area frumoas a elementelor gramaticii. Aici se
poate lua în calcul ³i supraînc rcarea operatorului specic.
5. ReadGrammar() - citirea tuturor elementelor gramaticii. Aici se poate
lua în calcul ³i supraînc rcarea operatorului specic.

II. Se cere denirea unei clase FiniteAutomaton

1
Membrii clasei vor : (Q, Σ, δ, q0 , F ) (daµi denumiri semnicative acestor
membri).
Observaµie: denirea trebuie s e sucient de general , încât s cuprind ³i
AFN ³i AFD.

Metodele clasei - obligatorii. (Pot exista ³i altele, dac este necesar)


1. VerifyAutomaton - veric dac este un automat valid. Aici trebuie
s identicaµi din teorie, care sunt veric rile necesare.
2. PrintAutomaton - a³area frumoas a elementelor unui automat. Aici
se poate lua în calcul ³i supraînc rcarea operatorului specic.
3. CheckWord - o funcµie care veric dac un cuvânt este acceptat sau
nu de un automat.
4. IsDeterministic - veric dac automatul este determinist sau nu.
III. Deniµi o funcµie care preia o gramatic regulat G ³i returneaz un obiect de
tip automat. Automatul returnat trebuie s recunoasc limbajul generat de
G. Funcµia poate  membr a clasei Grammar sau nu.

IV. În funcµia principal :


1. Se citesc din ³ier elementele unei gramatici regulate. Se veric dac
gramatica este corect ³i regulat . Numai în caz armativ meniul devine
disponibil.
2. Se creaz un meniu (care se a³az pân când nu mai sunt dorite opµiuni)
care permite:
(a) a³area gramaticii G
(b) generarea unui num r n de cuvinte în gramatica G
(c) obµinerea automatului echivalent cu G. Automatul echivalent se
a³eaz .
(d) vericarea dac un cuvânt este sau nu acceptat de în automatul
obµinut .
(e) generarea unui cuvânt în G + vericarea dac e acceptat de c tre
automat
V. BAREM:
1. Denire corect a clasei Grammar, cu membrii corespunz tori - 0.25pct
2. Metoda I. 1 - 0.5pct
3. Metoda I. 2 - 0.5pct

2
4. Metoda I. 3 - 2 pct, dac este complet rezolvat cf cerinµei
5. Metode I. 4 & I. 5 - 0.25 pct
6. Denire corect a clasei FiniteAutomaton, cu membrii corespunz tori -
0.25pct
7. Metoda II. 1 - 0.5pct
8. Metoda II. 2 - 0.25pct
9. Metoda II. 3 - 1.5pct
10. Metoda II. 4 - 0.5pct
11. Algoritm III - 2pct
12. Etapa IV - 0.5pct.

S-ar putea să vă placă și