Test
-
Upload
drawthelinemiru -
Category
Documents
-
view
212 -
download
0
description
Transcript of Test
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 auri = numarul de buri 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)