Limbaje Formale si Automate
2011 · Sesiune · CA/CB
Colectie de subiecte final + partial.
(Arhiva despre care vorbea Andrei Ismail la seminar)
Vezi attach-ul de mai jos!
6 decembrie 20111 fișier
Limbaje Formale si Automate
2011 · Sesiune · 332/333 CA
17 Ianuarie 2011
332 + 333 CA
1) Cum e limbajul L={a^n b^f(n) c^n | f(n) = n mod 5, n>=0}.
Justificati.
2)Demonstrati ca L = {0^i 1^j | i!=j} nu e limbaj regulat folosind
proprietati de inchidere.
3) Scrieti expresia regulata pentru L = {w din {0,1}* | w nu contine
101}. Explicati solutia pe scurt
4)Fie gramatica
S -> abSc | A
A -> cAd | cd
a) scrieti o derivare stanga pentru ababccddcc
b) ? L(G), justificati (nu demonstratie)
5) Fie L1,L2 limbaje Turing acceptate. Cum este L1UL2? Justificati
20 septembrie 2011
Limbaje Formale si Automate
2011 · Sesiune · 33x CB
31 Ianuarie 2011
1. Cum este limbajul L = {0^n1^m | n < 2m + 3, n si m > 0} ? // ceva
de genu..
2. Expr regulata pt limbajul ap {0,1}* in care fiecare grup par de 0
este urmat
de grup impar de 1 si fiecare grup impar de 0 este urmat de grup par
de 1
3. Se da un AFD. S.s.det. daca L complement pe care il accepta este
finit.
4. L regulat. Permut(L) cum este?
5. Masina Turing bidimensionala. Definire operatii.
6. Gramatica parantezarilor (doar paranteze rotunde si drepte,
parantezele, evident,
se deschid/inchid corect). Ex: (())[[][]][[[]]], [()]([()])...
20 septembrie 2011
Limbaje Formale si Automate
2011 · Sesiune · 331 CB
1 Februarie 2011
1.T = {0,1,(,),+,*,multimea vida,e} - simboli utilizati de expresiile regulate
(+ = reuniunea, * = Kleene star etc).
Scrieti GIC care genereaza expresia regulata peste alfabetul {0,1}
2.Dem L = {w.1^n , |w| = n } nu e regulat (Lema de pompare)
3.r,s - 2 expresii regulate .Se poate det algorimtul ,daca L(r) inclus
in L(s)? Cum ?
4.Se da gramatica G=S->ASB|cS|e A->a, B->b. L = L(G) . Descrieti L si
Lpar(cuv de lung para).Sa se modifica gramatica pt Lpar.
5.Dati ex :L1 reg , L2 nereg , L1+L2 reg
6.Fie L un limbaj acceptat de o MT. Descrieti masina turing care
accepta L*={w|w=w1w2....wn cu wi e L}.
20 septembrie 2011
Limbaje Formale si Automate
2011 · Sesiune · 334/335 CA
Subiecte ( 2.02.2011 ) 335CA + 334CA
1(?). Definim Maj(L1, L2, L3) = {multimea cuvintelor w care apar in cel putin din libajele L1, L2, L3 }. Demonstrati ca daca Maj(L1, L2, L3) este regulata daca L1, L2, L3
2. Daca L - LIC si S inclus in L . S neaparat LIC ? ( demonstratie )
3. L = {a^nb^n, c^m, n <= m <= 2n} . Demonstrati ca L != LIC .
4. L = {x1w1x2w2x3w3 ....xiwi+1} unde xi accepta siruri peste (c,d}* si wi accepta siruri de forma a^nb^n .
Descrieri GIC pentru L
Definiti APD-ul pentru gramatica de mai sus
5. Descrieti masina Turing care accepta siruri w peste {1, 2}* si lasa pe banda w' unde w' este urmatorul sir in ordine lexicografica
Precizari legate de subiect:
La 1 nu imi aduc foarte bine aminte enuntul .Poate ma corecteaza cineva . Era nevoie de demonstratie intr-un singur sens .
La 2 era nevoie practic doar de un contraexemplu ( gen L = a^nb^n si S = a^pb^p unde p e prim --> S nu e neaparat LIC)
3-ul era in This is Gold - pagina 27 ( unde coeficientul lui c era defapt i si nu m
La 4b) unde trebuia sa faci APD-ul, trebuia sa ii faci descrierea cu toate starile altfel nu primeai nimic . ( sau cel putin asa am fost avertizati inca de la inceputul examenului ).La începutul examenului am fost avertizați să nu facem un APD peste
șir, ci un APD din GIC-ul determinat la punctul a).
La 5 trebuia sa scrii in cuvinte cum arata masina Turing si cam ce operatii/stari faci .
Daca cumva am scris gresit la vreun exercitiu, va rog sa ma corecteze cineva de la 334/335.
Alte Precizari:
Examenul a avut 50 de minute.
Toate probleme au avut cate 10 puncte, exceptie facand problema 4 care a avut 20 de puncte ( 10 pentru fiecare subpunct ). Puteai acumula astfel in examen 60 de puncte dar era necesar 25 sa treci .
Corectarea mie mi s-ar parut foarte ok . ( De la noi nu cred ca a picat nimeni ) La noi a fost doar Diana la supraveghere . D-na profesoara a iesit din clasa vreo 30-40 de minute si nu a stat decat la inceput si la sfarsit . S-a putut vorbi cat de cat .
La corectare s-a tinut cont daca aveai peste 3 din seminar si se mai rotunjea la note ( de exemplu daca aveai nota X.1, X.2, X.3 se rotunjea la (X+1)). S-au luat note maricele .
--------------------------------------------------------------
Completari:
la 1. era :
"Definim Maj(L1, L2, L3) = {multimea cuvintelor w care apar in cel putin 2 din limbajele L1, L2, L3 }. Demonstrati ca daca Maj(L1, L2, L3) este regulata daca L1, L2, L3 sunt regulate"
la 2 a punctat chiar daca luai L regulat, nu LIC, desi la inceput zicea ca e gresit sa iei L regulat. Dar pentru siguranta, cand zice LIC, se refera la "clasa cea mai restrictiva e LIC".
4. i>0, n>0
5. era adunare in baza 2, dar cu 0 si 1 inlocuite de 1 si 2.
20 septembrie 2011
Limbaje Formale si Automate
2011 · Restanțe · CC
11 Septembrie 2011
1. AFD pt { w din {a,b}* | w nu contine 001 si are nr impar de simboluri }
2. L = {w din {a,b,c}* | #a(w) = #b(w) = #c(w)}. sa zici daca e LIC sau nu.
3. se dadeau niste gramatici si trebuia sa faci AS.
4. {xyx reverse | x,y din {a,b}*}. Ce fel de gramatica genereaza?
5. L1 si L2 limbaje neregulate. se poate ca reuniunea lor sa fie limbaj regulat?
20 septembrie 2011