Lucrarea de laborator № 2 Tema : „Automate finite”

1. Este dat automatul finit AF=(Q, , , q0, F). Reprezentaţi automatul sub formă de graf.2. Este sau nu automatul dat determinist?3. Dacă automatul este nedeterminist, construiţi automatul finit determinist echivalent.4. Construiţi gramatica regulată echivalentă cu AFD5. 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 respective.6. Pentru automatul finit AFD=(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. Scrieţi expresia regulată echivalentă.8. 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.9. Petru toate cele 5 şiruri obţinute construiţi aplicând lema de pompare descompunerea x=uvw.

Varianta 1AF=(Q, , , q0, F), Q = {q0, q1, q2}, = {a, b, c}, F = {q2}.(q0, a) = {q0}(q0, b) = {q1} (q0, b) = {q2} (q1, c) = {q1} (q1, c) = {q2} (q2, b) = {q2}

Varianta 2AF=(Q, , , q0, F),Q = {q0, q1, q2, q3}, ={a, b, c}, F ={q3}. (q0, a ) = {q0}

(q0, a ) = {q1}

(q0, a ) = {q2}

(q1, b ) = {q1} (q1, b ) = {q2} (q2, c ) = {q3}

Varianta 3AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3 }, = { a, b, c}, F = { q3 }.(q0, a ) = {q0}(q0, a ) = {q1} (q0, b ) = {q0} (q1, b ) = {q3} (q1, c ) = {q2} (q2, b) = {q3}

Varianta 4AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, a) = {q1} (q1, a) = {q2} (q2, b) = {q2} (q2, b) = {q3} (q2, c ) ={q2} (q3, a) ={q3}

Varianta 5AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, a) = {q1}

1

(q1, a) ={q2} (q2, c) = {q2} (q2, c) = {q3} (q2, b ) ={q2} (q3, a) ={q3}

Varianta 6AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, a) = {q1} (q1, b) ={q2} (q2, a) = {q2} (q2, a) = {q3} (q2, c ) ={q2} (q3, a) ={q3}.

Varianta 7AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, a) = {q1} (q1, b) ={q2} (q2, c) = {q2} (q2, c) = { q3} (q2, a ) ={q2} (q3, a) ={q3}

Varianta 8AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, b) = {q1} (q1, b) ={q2} (q2, c) = {q2} (q2, c) = {q3} (q2, a ) ={q2} (q3, b) ={q3}

Varianta 9AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, b) = {q1} (q1, b) ={q2} (q2, a) = {q2} (q2, a) = {q3} (q2, c ) ={q2} (q3, b) ={q3}

Varianta 10AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, b) = {q1} (q1, a) ={q2} (q2, a) = {q2} (q2, a) = {q3} (q2, c ) ={q2} (q3, b) ={q3}

2

Varianta 11AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, b) = {q1} (q1, a) ={q2} (q2, c) = {q2} (q2, c) = {q3} (q2, a ) ={q2} (q3, b) ={q3}

Varianta 12AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, b) = {q1}, (q1, a) ={q2} (q2, b) = {q2} (q2, b) = {q3} (q2, a ) ={q2} (q3, b) ={q3}

Varianta 13AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, c) = {q1} (q1, c) ={q2} (q2, b) = {q2} (q2, b) = {q3} (q2, a ) ={q2} (q3, c) ={q3}

Varianta 14AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, c) = {q1} (q1, c) ={q2} (q2, a) = {q2} (q2, a) = {q3} (q2, b ) ={q2} (q3, c) ={q3}

Varianta 15AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, c) = {q1} (q1, b) ={q2} (q2, a) = {q2} (q2, a) = {q3} (q2, c ) ={q2} (q3, c) ={q3}

Varianta 16AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, c) = {q1} (q1, b) ={q2}

3

(q2, c) = {q2} (q2, c) = {q3} (q2, a ) ={q2} (q3, c) ={q3}

Varianta 17AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, c) = {q1} (q1, a) ={q2} (q2, a) = {q2} (q2, a) = {q3} (q2, b ) ={q2} (q3, c) ={q3}

Varianta 18AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, c) = {q1} (q1, a) ={q2} (q2, b) = {q2} (q2, b) = {q3} (q2, a ) ={q2} (q3, c) ={q3}

Varianta 19AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, a) = {q1} (q1, c) ={q2} (q2, a) = {q2} (q2, a) = {q3} (q2, b ) ={q2} (q3, a) ={q3}

Varianta 20AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, a) = {q1} (q1, c) ={q2} (q2, b) = {q2} (q2, b) = {q3} (q2, a ) ={q2} (q3, a) ={q3}.

Varianta 21AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, a) = {q1} (q1, c) ={q2} (q2, b) = {q2} (q2, b) = {q3}

4

(q2, c ) ={q2} (q3, a) ={q3}

Varianta 22AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, a) = {q1} (q1, c) ={q2} (q2, c) = {q3} (q2, c) = {q3} (q2, b ) ={q2} (q3, a) ={q3}

Varianta 23AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, b) = {q1} (q1, c) ={q2} (q2, a) = {q2} (q2, a) = {q3} (q2, b ) ={q2} (q3, b) ={q3}

Varianta 24AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, b) = {q1} (q1, c) ={q2} (q2, b) = {q2} (q2, b) = {q3} (q2, a ) ={q2} (q3, b) ={q3}

Varianta 25AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, b) = {q1} (q1, c) ={q2} (q2, a) = {q2} (q2, a) = {q3} (q2, c ) ={q2} (q3, b) ={q3}

Varianta 26AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, b) = {q1} (q1, c) ={q2} (q2, c) = {q2} (q2, c) = {q3} (q2, a ) ={q2}

5

(q3, b) ={q3}

Varianta 27AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, b) = {q1} (q1, c) ={q2} (q2, b) = {q2} (q2, b) = {q3} (q2, c ) ={q2} (q3, b) ={q3}

Varianta 28AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, c) = {q1} (q1, a) = {q1} (q1, a) = {q2} (q1, c) ={q1} (q1, b) ={q3} (q2, b) ={q3}.

Varianta 29AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, c) = {q1} (q1, a) = {q2} (q1, a) = {q1} (q1, c) ={q1} (q1, a) ={q3} (q2, a) ={q3}

Varianta 30AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, a) = {q1} (q1, c) = {q1} (q1, c) = {q2} (q1, b) ={q1} (q1, a) ={q3} (q2, a) ={q3}.

Varianta 31AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, a) = {q1} (q1, b) = {q1} (q1, b) = {q2} (q1, c) ={q1} (q1, a) ={q3} (q2, a) ={q3}

6

Varianta 32AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, b) = {q1} (q1, c) = {q1} (q1, c) = {q2} (q1, a) ={q1} (q1, b) ={q3} (q2, b) ={q3}.

Varianta 33AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, b) = {q1} (q1, a) = {q1} (q1, a) = {q2} (q1, c) ={q1} (q1, b) ={q3} (q2, b) ={q3}.

Varianta 34AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, a) = {q1} (q1, c) = {q1} (q1, c) = {q2} (q1, b) ={q1} (q1, a) ={q3} (q2, b) ={q3}.

Varianta 35AF=(Q, , , q0, F), Q = {q0, q1, q2 , q3}, = { a, b, c}, F = { q3}. (q0, c) = {q1} (q1, a) = {q1} (q1, a) = {q2} (q1, c) ={q1} (q1, b) ={q3} (q2, b) ={q3}

7