> salut
> sunt anu 3 semestru unu si am lucrare la lfa - curs
> cu Irina Athanasiu
> cica din primele 5 cursuri
> are cineva idee ce se da?

   Din cate imi aduc aminte, parca s-a dat ceva de genul urmator ;)

<<Pentru fiecare dintre urmatoarele intrebari specificati daca este
adevarata sau falsa
 
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.>>
 

> are subiecte preferate?
> multumesc

   Cat despre faza cu zarul, iti recomand sa aduci o moneda - e mai
practic, date fiind conditiile.


  Bafta la test.


