Am primit urmatoarea foaie:

1.Care este expresia regulata care genereaza mult sirurilor peste alfabetul T={a,b} care se termina cu bab,
au lung para si nu incep cu aa

2.AF care accepta limbajul L={w|w din {a,b}* in care oricare 2 a-uri sunt separate prin 4k b-uri,k>0

3.PD care pt limbajul L={a^ib^ja^jb^i,i,j>0}
4.Descrieti functionarea mas T compusa pt L={xy|x,y din {a,b,c}*,|x|=|y| si #a(x)=#a(y)}
5. Pentru fiecare din intrebari, explicati raspunsul propus
1. Care este falsa:
a. exista gramatici regulate pentru care se pot construi gramatici ambigue
b. pentru orice limbaj finit se poate construi o expr reg care sa il genereze
c. nu exista lbj indep de context ptr care sa nu se poata construi gram neambigue

(c).
2. Care e falsa:
a. Un automat nedet poate sa accepte la momente diferite de timp lbje diferite ptr ca
ptr un ac sir pot avea evolutii diferite
b.fie R un limbaj regulat. Limbajul obtinut prin reuniunea tut prefixelor tut sirurilor din R este un LR
c. Diferenta a doua limbaje acceptate de automate finite nedet poate sa fie gen de o expresie regulata
(?:)

3. Limbajul {x E {0,1}* | x reprezinta o putere a lui 3 in binar } este:
a. acceptabil de un aut cu stiva nedet
b. acceptabil de un aut finit nedet
c. decidabil de o masina Turin
(c, e LFR)

4. Limbajul L4 = {a^ib^jc^kd^l | i =0 sau j = k = l} este
a. acceptabil de un aut cu stiva nedet
b. acceptat de un aut finit nedet
c. limbaj fara restrictii

(c)

5. Fie G o gram indep de context rec stg. Care din urm afirmatii e adev:
a. Nu se poate construi un analizator sintactic determinist descendent ptr limbajul generat de G
b. Gramatica G poate sa fie ambigua
c. Un compilator nu poate sa utilizeze un analizor sintactica construit pe baza G

Aici mie mi se pare ca am citit ceva asemanator cu : daca ma gramatica rec stg, pot face analiza descendenta
nedeterminista, deci am ales b.

asa arata foaia:
apoi s-au modificat subiectele 2 si 3 de la teorie(au fost scrise altele pe tabla:)
la 2:
L = {w|w din {a,b}* w nu contine aba si lungime (w) = para}
la 3.
L= {a^n w wr b^n} era nedeterminist dar simplu

In alta ordine de idei, la examen a fost liniste, dar poti copia (nu prea ai ce :)) ), profa si o asistenta au stat la catedra...
Multa bafta!
Laura

