walker
2104 palavras
9 páginas
Introdu¸˜o a Teoria da Computa¸˜o ca caSolu¸˜o da Terceira Lista de Exerc´ ca ıcios
Profa. Carmem Hara
Exerc´
ıcio 1:
Considere a gram´tica G abaixo: a S ⇒ ASB | ǫ
A ⇒ aAb | ǫ
B ⇒ bBa | ba
a. Mostre uma deriva¸ao mais a esquerda da palavra aabbba. c˜ S ⇒ ASB ⇒ aAbSB ⇒ aaAbbSB ⇒ aabbSB ⇒ aabbB ⇒ aabbba
b. Quantos passos de deriva¸ao tem o item (a). Resp: 6 c˜ c. Mostre uma deriva¸ao mais a direita da palavra abaabbbabbaa. c˜ S ⇒ ASB ⇒ ASbBa ⇒ ASbbaa ⇒ AASBbbaa ⇒ AASbabbaa ⇒ AAbabbaa ⇒ AaAbbabbaa ⇒ AaaAbbbabbaa ⇒
Aaabbbabbaa ⇒ aAbaabbbabbaa ⇒ abaabbbabbaa
d. Construa a ´rvore de deriva¸ao dos itens (a) e (c). a c˜
S
A
S
S
a
A
b
a
A
ε
B
A
b
a
A
B
ε
ε
b
A
a
A
b
a
b
a
S
A
b
(a)
S ε B b b a B b a a (c) ε e. Qual a linguagem definida pela gram´tica (L(G)) ? a Ln .Ln , onde n ≥ 0, L1 = {ai bi | i ≥ 0} e L2 = {bj aj | j > 0}
1
2
Exerc´
ıcio 2:
Construa uma gram´tica linear a direita que defina as linguagens abaixo. a a. (0 + 1)∗
Resp: S ⇒ ǫ | 0S | 1S
b. (0 + 1)(00 + 1)∗
Resp: S ⇒ 0A | 1A
A ⇒ 0B | 1A | ǫ
B ⇒ 0A
Exerc´ ıcio 3:
Considere a gram´tica G abaixo. a S ⇒ aSA | ǫ
A ⇒ bA | ǫ
a. Construa uma express˜o regular que defina L(G). a Resp: (ǫ + aa∗ b∗ )
b. Mostre que G ´ amb´ e ıgua.
Resp: basta mostrar duas ´rvores de deriva¸ao distintas para a mesma palavra (no exemplo, aab). a c˜
c. Construa uma gram´tica n˜o amb´ a a ıgua equivalente a G.
S ⇒ aAB | ǫ
A ⇒ aA | ǫ
B ⇒ bB | ǫ
1
S
S a S
a
S
a
A
ε
b
A
S
A
ε
ε
S
a
A
ε
A
b
A ε ε
Exerc´ ıcio 4:
Mostre que todos os s´ ımbolos da gram´tica G abaixo s˜o uteis. Construa uma gram´tica equivalente Gc sem a a ´ a transi¸oes em cadeia. Mostre que Gc cont´m s´ c˜ e ımbolos in´ teis. u G: S → A | CB
A → C |D
B → bB | b
C → cC | c
D → dD | d
S´
ımbolos que geram palavras (seqˆencis