Limbaje Formale

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

Ministerul Educaţiei şi Ştiinţei al Republicii Moldova

Universitatea Tehnică a Moldovei

Facultatea Calculatoare, Informatică şi Microelectronică