Limbaje Formale si Automate · 2015 · Sesiune

1. S -> AB | aaB

A -> a | Aa

B -> b

Este gramatica ambigua? Daca da, exista una echivalenta,

neambigua? Justificati.

2. L = { w apartine lui {a, b}*| |w| impar si w =/= w^R}

3. Fie L un limbaj regulat peste SIGMA. Scrieti un algoritm (pseudocod)

care sa afle daca L = SIGMA*.

4. Scrieti automat cu stiva care sa accepte

L = { w apartine lui {a, b}*| #b(w) = #a(w) + 3}.

5. Descrieti o masina Turing MT care primeste o alta m.T. M si un sir w

si decide daca w executa vreo operatie de mutare stanga la prelucrarea

lui w.

6. Scrieti un AFD minim care sa accepte

L = { w apartine lui {a, b}*| |w| par, oricare a este urmat de un nr. impar de b-uri}.

7. Fie AFD-ul urmator, descriind o multime regulata M:

(starile)

{q0, q1, q2}

(multimea de simboluri)

{0, 1}

(functia de tranzitie a starilor)

m(q0, 0) = q1

m(q1, 0) = q2

m(q2, 0) = q2

m(q2, 1) = q2

(starea initiala)

q0

(starea finala)

q2

Sa se descrie printr-o expresie regulata complementul lui M.