Nu mai stiu exact, dar cred ca s-a dat in vara la CA (cu Irina A.)


1.Fie GIC cu conditiile:

S-> AC
A->a
B->b
C->DD
D->AS|BS|a

Specificati APD a.i L(M)=L(G)

2. Construiti MT care copiaza elementele mod 3 ale unui ir
Ex: #aabaaaa# devine #aabaaaa#ba#

3. O progresie aritmetica este multimea { p+qn: n:0,1,...}
p,q din N. Aratati ca daca L inclus in {a}* si {n:a^n (- L} este o
progresie aritmetica atunci L este regulat.

4. Fie urmatorul limbaj peste (sigma) E = {0,1}*
L = {w1^n| w(- {0,1}*, |w| = n, n>= 0}
a). Scrieti o GIC pentru L
b). Aratati ca L nu este regulat, utilizand lema de pompare.

5. Demonstrati ca limbajul {a,b}* - { a^nb^n, n>= 0 } este LIC