ASTA S-A DAT LA CB in examen in vara:

1) Se da gramatica: G = (V, sigma, R, S) data de regulile: r = { S -> A|B
; A -> yA|x ; B -> x|y}. Care e expresia regulata care descrie limbajul
generat de gramatica ?

2) Se da limbajul: L = { a^m b^n | m!=n }. Este acesta limbaj independent
de context? Justificare.

3) Se da limbajul: L = {0^m 1^n | m > n > 0 }. Sa se arate cu ajutorul
lemei de pompare ca acest limbaj nu este regulat.

4) Sa se scrie gramatica care genereaza limbajul: L = { a^m b^p c^q | m =
p + 2*q }.

5) Sa se construiasca o masina Turing care sa decida (lasand #Y# sau #N#
pe banda) limbajul: L = { w apartine {a,b}* | #(w,a) = 2* #(w,b) }, adica
limbajul format din cuvintele in care numarul de a-uri este egal cu de 2 ori
numarul de b-uri.



//================================================================

O INCERCARE DE REZOLVARE DATA DE UN COLEG:

> 
> 1) Se da gramatica: G = (V, sigma, R, S) data de regulile:
> r = { S -> A|B ; A -> yA|x ; B -> x|y}. Care e expresia regulata
> care descrie limbajul generat de gramatica ?

Raluca a notat urmatoarele reguli:
S -> Ax | By
B -> x | y
A -> y | Ay

Pe care rezulta expresia regulata: yy*x | xy | yy

> 
> 2) Se da limbajul: L = { a^m b^n | m!=n }. Este acesta
> limbaj independent de context? Justificare.

Este LIC deoarece urmatoarea se poate scrie urmatoare gramatica:
S -> aBA | ACb
A -> aAb | e
B -> aB | e
C -> Cb | e

> 
> 3) Se da limbajul: L = {0^m 1^n | m > n > 0 }. Sa se
> arate cu ajutorul lemei de pompare ca acest limbaj nu este regulat.
>

Se face similar exemplului de la curs(trei cazuri care doar toate
false => limbajul nu e regulat).

> 4) Sa se scrie gramatica care genereaza limbajul:
> L = { a^m b^p c^q | m = p + 2*q }.

Una din cele mai simple variante:
S -> aaSc | A | e
A -> aAb | e

> 5) Sa se construiasca o masina Turing care sa decida
> (lasand #Y# sau #N# pe banda) limbajul:
> L = { w apartine {a,b}* | #(w,a) = 2* #(w,b) }, adica
> limbajul format din cuvintele in care numarul de a-uri este egal cu de 2 ori
> numarul de b-uri.

L(#,a) se fac deplasari la stanga pana cand se intalneshte un # sau un
a. Intai se face deplasarea shi apoi testul.
c se scrie c pe banda(similar se scrie #, Y shi N)

Initzial pe banda se afla #....# cu capul pozitionat pe ultimul #.
