Asta s-a dat in toamna la restanta (cu Irina A.):


1. a) Sa se scrie o expresie regulata pentru limbajul cuvintelor formate
din {0, 1} ce nu contin 3 de 0 consecutiv. b) Sa se scrie un AF pt
expresia regulata.
2. Sa se construiasca un APD care accepta cuvinte w = a^i * b^j * c^k cu
i!=j SAU j!=k.
3. Care este limbajul generat de: S-> bSS|a. Demonstratie prin inductie.
4. Sa se demonstreze folosind lema de pompare ca limbajul: L = {a^m *
b^n * c^nm, m, n >= 0} nu e LIC.
5. Sunt masinile turing LR (left-right) si RL (right-left) echivalente?

Asta pentru 45 de minute. Pentru inca 30 de minute se putea da marire
sau recupera cele 3 puncte de la seminar:

1. Ce legatura exista intre MTS (masina turing standard) si MTN (masina
turing nedeterminista) dpdv al decidabilitatii?
2. Sa se demonstreze ca limbajele regulate sunt inchise in raport cu
REVERSE (rasturnat).