Exercícios resolvidos sobre gramática livre-do-contexto do 1º/2014

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 3
Construa uma grama´tica livre-do-contexto que gere a linguagem
1. L = {0i1j0k| i, k ≥ 0 e j > i + k}
Resposta:
S → ABC
A → 0A1 | ε
B → 1B | 1
C → 1C0 | ε
2. L = {aibjck| i, j, k ≥ 0 e i = j ou i = k}
Resposta:
S → S1 | S2
S1 → TX
T → aTb | ε
X → cX | ε
S2 → aS2c | R
R → bR | ε
3. L(R), com R = (00)∗1(110)∗
Resposta:
S → S11S2
S1 → S100 | ε
S2 → S2110 | ε
4. L = {w| w ∈ {0, 1}∗, w tem comprimento ı´mpar, e o primeiro s´ımbolo, o u´ltimo s´ımbolo e
o s´ımbolo do centro sa˜o iguais}. Note que 0 ∈ L e 1 ∈ L.
Resposta:
S → 0A0 | 1B1 | 0 | 1
A → 0A0 | 0A1 | 1A0 | 1A1 | 0
B → 0B0 | 0B1 | 1B0 | 1B1 | 1