DAT LA CA IN VARA (cu Irina A.):


1. Fie L = { w apartine {0,1,2}* | n0(w) + n1(w) + n2(w) = numar prim }.
Demonstrati ca L nu este LIC (limbaj independent de context). 

(n0(w) inseamna numarul de 0-uri care apar in w; mai simplu, n0+n1+n2 e
lungimea sirului w; se dem. cu lema de pompare) 

2. Construiti AFD minim pentru automatul: 
[aici ar fi trebuit sa apara o figura] 

3. Fie L un limbaj acceptat de un AFN. Este L acceptat de o masina
Turing determinista? Este L decis de o MTD? Justificare. 

4. Se considera limbajul parantezelor bine inchise. Care este cel mai
simplu acceptor pentru acest limbaj, in cazurile: 

a) un singur tip de paranteze; (de ex. ( si )) 
b) mai multe tipuri de paranteze (de ex. {, }, [, ], (, ) ); 

Schitati acceptorul pentru fiecare caz (descriere, nu specificarea
completa a functiei de tranzitie). 

5. Dati un exemplu de gramatica care nu este LL(1). Demonstratie. 
