Test 2 LFA

Nu uitati sa va semnati!

(1p) 1. Fie L ­ LIC si L’ = . Dem ca L’ nu este neaparat LIC.w | w wR ∈ L

(1p) 2. Scrieti GIC pt L = k natural, w are acelasi simbol pe | |w| 2k 1,w ∈ a, b * = + prima pozitie si la mijloc.

(1p) 3. Exista un limbaj care sa satisfaca simultan urmatoarele conditii? (daca da dati un exemplu, altfel demonstrati prin reducere la absurd ca nu exista)

L ­ limbaj regulat peste alfabetul a,b L =/ ⊘ Pentru orice sir din L, numarul de a­uri = numarul de b­uri Pentru orice w din L, LwR ∈ Niciun sir din L nu contine subsirul “ab”.

(1p) 4. Demonstrati utilizand lema a doua de pompare ca urmatorul limbaj nu este independent de context: L = , n >= 0.b aan n n

(1p) 5. Fie L = , n < 5. Este regulat? (Daca da, scrieti AFN/AFD/ER, daca nu ban n demonstrati folosind lema de pompare)

(1p) 6. Fie L = , n,m > 0. Ce se poate spune despre L? (in cel mai strict sens)b cam n 2n

(1p) 7. Care este valoarea de adevar a afirmatiei:Pentru orice limbaj regulat L exista un limbaj neregulat L’ a.i L L’? (Justificati)⊆

(1p) 8. Fie L = , j = i + k; i, k > 0. Ce se poate spune despre L? (in cel mai strict b cai j k sens)

(1p) 9. Fie L limbajul cuvintelor formate din 0,1 ce nu contin 3 de 0 consecutiv. Ce se poate spune despre L? (in cel mai strict sens)

(1p) 10. Fie urmatoarea gramaticaS ­> aaS | eCare este limbajul generat de gramatica? Este regulat? (Justificati)