
ASTA ERA PARCA LA LUCRAREA DE CURS cred



1. Limbajul {0+ 0n 1* 1n| n > 0} este regulat.

R: Adevarat. Limbajul este : 00+1+.

2. Orice limbaj regulat poate sa fie acceptat de AFD cu o singura stare
de acceptare.

R: Fals. Fie L1 = { w| w in {a,b}*, |w| este divizibil cu 3}

si L2 { w| w in {c,d}* |w| este divizibil cu 3} L = L1 reunit cu L2
este regulat dar

este acceptat numai de un AFD cu doua stari finale.

3. Daca L este regulat si L-R este regulat atunci R este regulat

R: Fals. Daca L este multimea vida, pentru orice multime L - R este
multimea vida.

Adica R poate sa fie orice limbaj

4. Daca A este un subset din B si B este un subset din C si A si C sunt
regulate atunci 

B este regulat

R: Fals. Orice limbaj peste {a, b} este un subset din (a+b)*

si un super set al multimii vide, dar nu orice limbaj peste 

{a, b} este regulat

5. Daca r si s sunt expresii regulate atunci (r+ + rs+)+=r(r++sr+)* 

R: Fals. Limbajul din stanga contine rs in timp ce cel din dreapta nu
contine

rs

6. Limbajul L = PREFIX(L)SUFFIX(L)

R: Fals. Fie L = a*b*, PREFIX(a*b*)=SUFFIX(a*b*)=a*b* adica

PREFIX(a*b*)SUFFIX(a*b*)=a*b*a*b*, ceea ce este alt limbaj decat L

7. Multimea limbajelor regulate este infinit nenumarabila

R: Fals. Limbajele regulate sunt infinit numarabile. Se poate

demonstra prin considerarea operatiilor prin care

se construiesc expresiile regulate care genereaza

limbaje regulate. Expresiile regulate se pot "numerota".

8. Limbajul {zRwwRvvRz : w I {a,b}*, v I {a,c}*, si z I {b,c}*} este LIC

R: Adevarat 

S -> bSb | cSc | WV 

W -> aWa | bWb | l

V -> aVa | cVc | l

9. Limbajul {w I {a,b, c,d}* numarul de a-uri = numarul de b-uri si
numarul de c-uri 

este egal cu numarul de d-uri} este LIC

R: Fals. Se poate demonstra rin lema de pompare alegand sirul ancnbndn,
etc.

10. Daca complementul limbajului L este LIC dar nu regulat atunci L nu
poate sa fie regulat.

R: Adevarat. Complementul limbajului L nu este regulat, multimea
limbajelor

regulate este inchisa la complementare deci L nu poate sa fie regulat

11.Daca L1 este LIC si L2 nu este LIC atunci L1 intersectat cu L2 nu
este LIC

R: Fals

L1 un limbaj peste {a,b,c} si L2 un limbaj peste {d, e, f}. Intersectia
lor este multimea 

vida deci un limbaj regulat

12. Daca complementarul unui limbaj L nu este LIC atunci L nu este LIC

R: Fals. L = {ww| w in {a,b}*} nu este LIC dar limbajul complementar
este LIC

13. Limbajul {a,b}* - {anbn}n >0} este LIC

R: Adevarat

S -> ((a|b)(a|b))*(a|b)|AA|BB|BA

A -> aAa|aAb|bAa|bAb|a

B-> aBa|aBb|bBa|bBb|b

Notatia ((a|b)(a|b))*(a|b)este o prescurtare a gramaticii care descrie
limbajul

regulat al sirurilor de a si b cu numar impar de elemente si care sigur
nu sunt de forma:

anbn, etc.

14. Fie L un limbaj regulat orice L' inclus in L este regulat 

R: Fals. L = {0,1}* este un limbaj regulat nu orice limbaj inclus in L
este regulat

15. Daca L1 este regulat si reuniunea L1, L2 este un limbaj regulat
atunci L2 este regulat 

R: Fals. Daca L1 = {0,1}* atunci pentru orice limbaj L2 inclus in L1, L1
reunit cu L2 = L1.>>
