1. L1L2 regulat (doua limbaje concatenate), L1
regulat, atunci L2 regulat? (demonstratie sau
contraexemplu)
fals - L1 = a^n cu n>=0; L2= a^p cu p prim; daca le
concatenez, imi da ceva a^m cu m>=0 si asta e regulat
dar L2 nu e regulat;

2.sa se faca automatul care accepta un numar egal de
01 si 10 (adica 101 este acceptat dar 1010 nu este)

st. 0  1
q0 q1 q2
q1 q1 q3
q3 q1 q3
q2 q4 q2
q4 q4 q2
(eu l-am desenat dar in asta nu stiu cum sa desenez)

3. L este LIC, S inclus in L, atunci S este LIC?

nu, L este a^n cu n>=0, S este a^p cu p prim, S inclus
in L dar S nu este LIC;

4.L este a^n.b^2n.c^n; este LIC
nu, cu teorma de pompare

5 L este a^i.b^j.c^k.d^l.a^l.b^k.c^j.d^i; este LIC
da, se construieste gramatica regulata:
s->aAd|A
A->aAd|bBc|B
B->bBc|cCb|C
C->cCb|dDa|D
D->dDa|lambda
gramatica asta genereaza limbajul L, gramatica este IC
deci L este LIC

6.s->wA|Bw|w
este regulata?

nu pt ca gramaticile sunt regulate dreapta (adica au
neterminali in dreapta - cred) sau regulate stanga
(adica au neterminali in stanga); nu se poate sa am
neterminali si in stanga si in dreapta cum sunt
pozitionati A si B aici.

7. sa se construiasca masina turing care face
f(x,y,z)=0 pt x=y+z, 1 pt x>y+z si 2 pt x<y+z;
numerele sunt in forma unara, am voie sa pun si alte
simboluri decat I si #

asta e desenat si nu se poate; nu e prea complicat -
intai adun y cu z pe banda si apoi compar x cu
rezultatul: daca am #y#z#x# pt adunare fac ##yz#x -
adica mut un diez, pe cel dintre y si z; dupa asta fac
compararea.


comentarii - am luat 9 din 8.60 - gresise formula la
inceput si ieseau note mai mici - asa ca atentie,
refaceti calculele voi. imi punctase 2 pct proiectul
desi imi alesesem proiect de 2,5pct - asa ca atentie
si la asta. daca au fost probleme, s-a putut discuta
cu asistentul si a mai marit niste punctaje (in
principal la MT pt ca nu intelesese ce faceam - faceti
compunere cu toate cele trei parti: introducere,
cuprins si incheiere si abia pe urma rezolvarea). in
timpul examenului nu prea s-a vorbit desi nu an tipat
nimeni la noi (se poate schimba un raspuns sau doua
daca stati pe sus). ne-a lasat cam 1h si 10 min. eu
mai vroiam timp dar nu invatasem f. mult asa ca pt
unu' care invata e destul.

in rest, bafta - trimit mail-ul asta la cunoscuti,
daca aveti prieteni la cb care fac cu Lorina LFA
trimiteti mai departe.


__________________________________
Do you Yahoo!?
Yahoo! Calendar - Free online calendar with sync to Outlook(TM).
http://calendar.yahoo.com