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

Prévia do material em texto

Autoˆmatos e Computabilidade – Teste 3
Sejam L uma linguagem livre-do-contexto. Prove que a linguagem L∗ tambe´m e´ livre-do-contexto.
Indique se cada uma das seguintes afirmac¸o˜es e´ verdadeira ou falsa. Se e´ verdadeira, explique por
queˆ. Se e´ falsa, fornec¸a um contraexemplo.
1. Toda linguagem regular e´ livre-do-contexto.
2. Toda linguagem livre-do-contexto e´ regular.
1. Considere a grama´tica livre-do-contexto definida por
S → AB
A → aA | ε
B → ab | bB | ε
Cada derivac¸a˜o de uma cadeia deve comec¸ar pela substituic¸a˜o S ⇒ AB. Claramente, cada
cadeia derivada de A possui uma u´nica derivac¸a˜o poss´ıvel a partir de A. Similarmente,
cada cadeia derivada de B possui uma u´nica derivac¸a˜o poss´ıvel a partir de B. Portanto, a
grama´tica na˜o e´ amb´ıgua. Esta conclusa˜o e´ verdadeira ou falsa? Justifique sua resposta.
Resposta: A conclusa˜o e´ falsa. Por exemplo, a cadeia ab possui duas derivac¸o˜es mais a`
esquerda diferentes : (1) S ⇒ AB ⇒ aAB ⇒ aB ⇒ abB ⇒ ab e (2) S ⇒ AB ⇒ B ⇒
ab.
2. A grama´tica livre-do-contexto G, definida por
S → SS | aSb | ε,
gera a linguagem L(G). Construa uma grama´tica livre-do-contexto G1 na forma normal de
Chomsky que gere a linguagem L(G)− {ε}.
Resposta: Convertemos G a` forma normal de Chomsky seguindo o me´todo visto em
aula (livro de Sipser, pa´gina 111), e logo eliminamos uma regra que permite derivar a
cadeia vazia apartir da varia´vel inicial. O resultado e´
S1 → SS | U2U1 | U2U3
S → SS | U2U1 | U2U3
U1 → SU3
U2 → a
U3 → b
3. Seja L a linguagem gerada pela grama´tica livre-do-contexto G = (V,Σ, R, S). Construa
uma grama´tica livre-do-contexto G1 que gere a linguagem L
∗.
Resposta: Criamos uma nova varia´vel S1 /∈ V , que sera´ a varia´vel inicial de G1, e
adicionamos a regra S1 → S1S | ε. Formalmente, G1 = (V1,Σ, R1, S1), com V1 = V ∪{S1}
e R1 = R ∪ {S1 → S1S, S1 → ε}.
4. Construa uma grama´tica livre-do-contexto que gere a linguagem reconhecida pelo AFD
q1 q2 q3
q4
a
b
b
a
a
b
a,b
Resposta: Definimos quatro varia´veis S,A,B e C, que correspondem aos estados
q1, q2, q3 e q4 do AFD, respectivamente. Seguindo o me´todo visto em aula, obtemos a
grama´tica
S → aA | bC | ε
A → aA | bB
B → aA | bB | ε
C → aC | bC
5. Construa uma grama´tica livre-do-contexto que gere a linguagem L = {ambn| 0 ≤ n < 2m}
sobre o alfabeto Σ = {a, b}. Atenc¸a˜o: note que ε /∈ L.
Resposta: Por exemplo, a seguinte grama´tica gera L
S → aSbb | aS |ab | a