la ex 1 0 este inlocuit cu 00 (0->00), nu cu 010 ;)

--- Moise Georgiana <mgeorgianaelena@yahoo.com> wrote:

> 1.Fie w apartine {0,1} un sir . Definim dublu(w)
> sirul format prin
> inlocuirea 0->010; 1->11_ . Fie L un limbaj acceptat
> AFD. Specificato
> AFD care accepta dublu(L)={dublu(w)| W ap L}
>
> 2. Fie E un alfabet si F o mult finita de siruri din
> E. Dem ca
> limbajul format din siruri din E care nu contin
> siruri din F este regulat
>
> 3. Avem APD determinist. Este complementul
> limbajului acceptat de APD
> lic? - raspuns DA
>
> 4.Scrieti o procedura care sa determine daca
> complementul lb acceptat
> pt un AFD este finit
>
> 5.{a^ib^j | j=i^2 } nu e LIC
>
> 6. Sa se scrie gramatica pt limbajul care are nr de
> 0 > nr de 1
>
> 7. M' -> MT care nu se deplaseaza la stanga. Ce fel
> de limbaje accepta?
> Raspuns: LR
> 

 1. Fie un AFD m care are n stari. Pp. ca exista un cuvant w a.i. |w|>n este acceptat de M. Demonstrati ca M accepta un limbaj infinit.
 
2. Fie L={w in {a,b}* |w nu contine 2 a adiacenti; fiecare b este adiacent unui alt b; |w| par}. Dem. ca L = regulat.
 
3. Descrieti o procedura care sa determine daca un AFD dat accepta toate sirurile peste un alfabet specificat.
 
4. Construiti gramatica pt L={a^i*b^j*c^k|j=i+k}
 
5. Construiti un APD M ai L(G)=L(M) si G:
        S->aAA; A->aS|bS|a
6. Utilizati proprietatea de inchidere fata de reuniune pt a dem ca limbajul {a^m*b^n|n<>m} este LIC
7 Justificati ca MT care isi muta capul doar la dreapta sau se resteaza in pozitia de start este la fel de puternica precum MTS.