compiladores

Gramáticas, Expressões Regulares, Bombeamento e Propriedades

1) Identifique as linguagens que são geradas pelas gramáticas a seguir (nem todas as gramáticas abaixo são gramáticas regulares):

a) G1 = ({P, Z}, {0, 1}, R1 , P ).
R1:
P => 0P1 | Z
Z => 0Z | 0 b) G2 = ({P, Z, U}, {0, 1}, R2 , P).
R2:
P => 0P1 | Z | U
Z => 0Z | 0
U => U1 | 1 c) G3 = ({S, X}, {0, 1}, R3 , S).
R3:
S => 00S | 1X | λ
X => 00X | 1S

d) G4 = ({P, X}, {a, b, c}, R4, P).
R4:
P => aPa | X
X => bXc | Xc | λ e) G5 = ({P, A, B, F}, {a, b}, R5, P).
R5:
P => aAP | bBP | F
Aa => aA
Ab => bA
Ba => aB
Bb => bB
AF => Fa
BF => Fb
F => λ

f) G6 = ({P}, {0, 1}, R6, P).
R6:
P => 0P1 | λ
01 => 10

2) Obtenha gramáticas regulares para as seguintes linguagens:
a) {0}{11}*{0}
b) {w  {0, 1, #}* | toda seqüência de 0's em w vem entre dois #s}.
c) O conjunto das palavras sobre {0, 1} de tamanho par com pelo menos dois 1s.

3) Obtenha expressões regulares e gramáticas regulares para as seguintes linguagens:
a) {w  {a, b}* | |w| # {0, 2, 4}}.
b) {w  {a, b}* | w conté apenas um ou dois b´s}.
c) {w  {a, b, c}* | o número de a´s mais o de b´s em w é par}.
d) {w  {a, b, c}* | w não termina com cc}.
e) {w  {a, b}* | w contém b e |w| mod 3 = 1} 4) Obtenha expressões regulares que denotem as linguagens sobre {0, 1} abaixo, a partir de AFs que reconheçam as mesmas.
a) O conjunto das palavras em que 0s só podem ocorrer nas posições pares.
b) O conjunto das palavras com pelo menos um símbolo em que os 0´s, se houver algum 0, precedem os 1´s, se houver algum 1.
c) O conjunto das palavras que não contém a subpalavra 000.

5) Prove que os seguintes conjuntos não são linguagens regulares, utilizando o lema do bombeamento:
a) {0k12k | k  1}.
b) {x1n | n  0, x  {0, 1}* e |x| = n}.
c) {0k1n0k | k, n  0}.

6) Seja L uma linguagem não regular, R uma regular e F uma linguagem finita. Mostre que é sempre regular, sempre não