alguns exercicios

Prévia do material em texto

Gramáticas Livre do Contexto
Linguagens Formais e Autômatos
http://www.ybadoo.com.br/
G1 = ({atr, exp, id}, {A, B, C, :=, +, *, (, )}, P1, atr)
P1 = { <atr> → <id> := <exp>
<exp> → <id> + <exp> | <id> * <exp> | ( <exp> ) | <id>
<id> → A | B | C }
01. [Sebesta, 2000] Apresente uma derivação à extrema esquerda da sentença A := A * (B + (C * A))
sobre a gramática G1.
02. [Sebesta, 2000] Apresente uma derivação à extrema direita da sentença A := A * (B + (C * A))
sobre a gramática G1.
03. [Sebesta, 2000] Apresente uma árvore de derivação da sentença A := A * (B + (C * A)) sobre a
gramática G1.
04. [Sebesta, 2000] Apresente uma derivação à extrema esquerda da sentença B := C * (A * C + B)
sobre a gramática G1.
05. [Sebesta, 2000] Apresente uma derivação à extrema direita da sentença B := C * (A * C + B)
sobre a gramática G1.
06. [Sebesta, 2000] Apresente uma árvore de derivação da sentença B := C * (A * C + B) sobre a
gramática G1.
07. [Sebesta, 2000] Apresente uma derivação à extrema esquerda da sentença A := A * (B + (C))
sobre a gramática G1.
08. [Sebesta, 2000] Apresente uma derivação à extrema direita da sentença A := A * (B + (C)) sobre a
gramática G1.
09. [Sebesta, 2000] Apresente uma árvore de derivação da sentença A := A * (B + (C)) sobre a
gramática G1.
G2 = ({atr, exp, ter, fat, id}, {A, B, C, :=, +, *, (, )}, P2, atr)
P2 = { <atr> → <id> := <exp>
<exp> → <exp> + <ter> | <ter>
<ter> → <ter> * <fat> | <fat>
<fat> → ( <exp> ) | <id>
<id> → A | B | C }
10. [Sebesta, 2000] Apresente uma derivação à extrema esquerda da sentença A := (A + B) * C sobre a
gramática G2.
11. [Sebesta, 2000] Apresente uma derivação à extrema direita da sentença A := (A + B) * C sobre a
gramática G2.
1 de 8
Gramáticas Livre do Contexto
Linguagens Formais e Autômatos
http://www.ybadoo.com.br/
12. [Sebesta, 2000] Apresente uma árvore de derivação da sentença A := (A + B) * C sobre a
gramática G2.
13. [Sebesta, 2000] Apresente uma derivação à extrema esquerda da sentença A := B + C + A sobre a
gramática G2.
14. [Sebesta, 2000] Apresente uma derivação à extrema direita da sentença A := B + C + A sobre a
gramática G2.
15. [Sebesta, 2000] Apresente uma árvore de derivação da sentença A := B + C + A sobre a
gramática G2.
16. [Sebesta, 2000] Apresente uma derivação à extrema esquerda da sentença A := A * (B + C) sobre a
gramática G2.
17. [Sebesta, 2000] Apresente uma derivação à extrema direita da sentença A := A * (B + C) sobre a
gramática G2.
18. [Sebesta, 2000] Apresente uma árvore de derivação da sentença A := A * (B + C) sobre a
gramática G2.
19. [Sebesta, 2000] Apresente uma derivação à extrema esquerda da sentença A := B * (C * (A + B))
sobre a gramática G2.
20. [Sebesta, 2000] Apresente uma derivação à extrema direita da sentença A := B * (C * (A + B))
sobre a gramática G2.
21. [Sebesta, 2000] Apresente uma árvore de derivação da sentença A := B * (C * (A + B)) sobre a
gramática G2.
22. [Sebesta, 2000] Considerando a gramática G3, quais das seguintes sentenças estão na linguagem gerada
por essa gramática?
G3 = ({S, A, B}, {a, b}, P3, S)
P3 = { <S> → <A> a <B> b
<A> → <A> b | b
<B> → a <B> | a }
a) baab b) bbbab
c) bbaaaaa d) bbaab
e) baba
2 de 8
Gramáticas Livre do Contexto
Linguagens Formais e Autômatos
http://www.ybadoo.com.br/
23. [Sebesta, 2000] Considerando a gramática G4, quais das seguintes sentenças estão na linguagem gerada
por essa gramática?
G4 = ({S, A, B}, {a, b, c, d}, P4, S)
P4 = { <S> → a <S> c <B> | <A> | b
<A> → c <A> | c
<B> → d | <A> }
a) abcd b) acccbd
c) acccbcc d) acd
e) accc
G5 = ({A, B, C}, {x, +, *}, P, A)
P5 = { <A> → <A> + <B> | <B>
<B> → <B> * <C> | <C>
<C> → x }
24. Apresente uma derivação à extrema esquerda da sentença x * x + x sobre a gramática G5.
25. Apresente uma derivação à extrema direita da sentença x * x + x sobre a gramática G5.
26. Apresente uma árvore de derivação da sentença x * x + x sobre a gramática G5.
27. Apresente uma derivação à extrema esquerda da sentença x * x + x * x sobre a gramática G5.
28. Apresente uma derivação à extrema direita da sentença x * x + x * x sobre a gramática G5.
29. Apresente uma árvore de derivação da sentença x * x + x * x sobre a gramática G5.
G6 = ({S, A, B, C}, {x, y, z, +, *, (, )}, P6, S)
P6 = { <S> → <S> + <S> | <A>
<A> → <A> * <A> | <B>
<B> → ( <S> ) | <C>
<C> → x | y | z }
30. Apresente uma derivação à extrema esquerda da sentença x + ( y * ( z * x ) + z ) sobre a
gramática G6.
31. Apresente uma derivação à extrema direita da sentença x + ( y * ( z * x ) + z ) sobre a
gramática G6.
32. Apresente uma árvore de derivação da sentença x + ( y * ( z * x ) + z ) sobre a gramática G6.
3 de 8
Gramáticas Livre do Contexto
Linguagens Formais e Autômatos
http://www.ybadoo.com.br/
33. Apresente uma derivação à extrema esquerda da sentença x * ( y + z ) sobre a gramática G6.
34. Apresente uma derivação à extrema direita da sentença x * ( y + z ) sobre a gramática G6.
35. Apresente uma árvore de derivação da sentença x * ( y + z ) sobre a gramática G6.
36. Quais das gramáticas abaixo são ambíguas? Apresente a árvore de derivação para comprovar a
ambiguidade.
a) G = ({S, T, F}, {a, b, c, +, *}, P, S)
P = { <S> → <S> + <S> | <T>
<T> → <T> * <T> | <F>
<F> → a | b | c }
b) G = ({S, T, F}, {a, b, c, +, *, (, )}, P, S)
P = { <S> → <S> + <T> | <S> * <T> | <T>
<T> → ( <S> ) | <F>
<F> → a | b | c }
c) G = ({S, T, F}, {a, b, c, +, *}, P, S)
P = { <S> → <S> + <T> | <T>
<T> → <T> * <T> | <F>
<F> → a | b | c }
37. Desenvolver uma Gramática Livre do Contexto (GLC) que reconheça a declaração de variáveis utilizada
pela linguagem de programação Java, para os tipos inteiros e reais, como nos exemplos abaixo:
int a;
double b, c, d;
int soma = 0;
double produto = 1, media, def5;
38. Desenvolver uma Gramática Livre do Contexto (GLC) que reconheça programas desenvolvidos na
linguagem de programação SIMPLE, especificada em http://www.jacinto-mendes.eti.br/mackenzie/
compiladores/simpletron/simpletron03.htm. 
39. Construa uma Gramática Livre do Contexto (GLC) sobre o alfabeto {a, b, c} que reconheça a linguagem
formal L = {anb2nc, n ≥ 0}. Exemplo de palavras que a gramática livre do contexto deve reconhecer:
c
abbc
aabbbbc
aaabbbbbbc
40. Construa uma Gramática Livre do Contexto (GLC) sobre o alfabeto {a, b, c} que reconheça palavras
palíndromas, ou seja, palavras que lidas da esquerda para a direita ou vice-versa são a mesma palavra.
41. Desenvolver uma Gramática Livre do Contexto (GLC) sobre Σ = {a, b, c}, que reconheça a linguagem L =
{w | w possui acc como prefixo, cba ou cac como subpalavra e acb como sufixo}.
4 de 8
Gramáticas Livre do Contexto
Linguagens Formais e Autômatos
http://www.ybadoo.com.br/
42. Desenvolver uma Gramática Livre do Contexto (GLC) sobre Σ = {a, b, c}, que reconheça a linguagem L =
{w | w possui bac ou cbc como prefixo, bca ou caa como subpalavra e abc ou cac como sufixo}.
43. Desenvolver uma Gramática Livre do Contexto (GLC) sobre Σ = {a, b, c}, que reconheça a linguagem L =
{w | w possui bbc ou acc como prefixo, cab ou bcb como subpalavra e bba ou abc como sufixo}.
44. Desenvolver uma Gramática Livre do Contexto (GLC) sobre Σ = {x, y, z}, que reconheça a linguagem L =
{w | w possui xy como prefixo, yzx como subpalavra e xzx como sufixo}.
45. Desenvolver uma Gramática Livre do Contexto (GLC) sobre Σ = {a, b, c}, que reconheça a linguagem L =
{w | w possui acb ou cac como prefixo, baa ou cba como subpalavra e acb ou bac como sufixo}.
46. Desenvolver uma Gramática Livre do Contexto (GLC)sobre Σ = {x, y, z}, que reconheça a linguagem L =
{w | w possui xxy ou yyz como prefixo, yxz ou yzx como subpalavra e xzz ou xyx como sufixo}.
47. Desenvolver uma Gramática Livre do Contexto (GLC) sobre Σ = {a, b, c}, que reconheça a linguagem L =
{w | w possui abc ou cba como prefixo, acc ou abb como subpalavra e cbb ou caa como sufixo, caso
a subpalavra seja acc, e bab ou bcb como sufixo, caso a subpalavra seja abb}.
48. Desenvolver uma Gramática Livre do Contexto (GLC) sobre Σ = {1, 2, 3}, que reconheça a linguagem L =
{w | w possui 132 ou 223 como prefixo, 232 ou 312 como subpalavra e 121 ou 321 como sufixo}.
49. Desenvolver uma Gramática Livre do Contexto (GLC) sobre Σ = {a, b, c}, que reconheça a linguagem L =
{w | w possui ab como prefixo, bca como subpalavra e aca como sufixo}.
50. Desenvolver uma Gramática Livre do Contexto (GLC) sobre Σ = {x, y, z, w}, que reconheça a linguagem L
= {w | w possui xyw ou wzz como prefixo, wzx ou wyx como subpalavra e xyy ou xwz como sufixo}.
51. Desenvolver uma Gramática Livre do Contexto (GLC) sobre Σ = {x, y, z}, que reconheça a linguagem L =
{w | w possui xyz como prefixo, zxy como subpalavra e xyx como sufixo}.
52. Desenvolver uma Gramática Livre do Contexto (GLC) sobre Σ = {a, b, c}, que reconheça a linguagem L =
{w | w possui cba como prefixo, aba como subpalavra e abc como sufixo}.
53. Desenvolver uma Gramática Livre do Contexto (GLC) que reconheça expressões de adição e subtração na
linguagem de programação LISP, considerando que os operandos sejam apenas números inteiros,
números reais e variáveis. Uma variável é uma palavra composta por dígitos e letras, cujo primeiro símbolo
deve ser obrigatoriamente uma letra. A seguir são apresentados algumas expressões válidas como
exemplo.
(+ 1 a 2 )
(- b5 -2 1.9 )
(+ x (- 1 2 3) soma )
(- a 10 (+ 1.5 -5 (- s123 b432) -0.5 4) 123 bgty)
5 de 8
Gramáticas Livre do Contexto
Linguagens Formais e Autômatos
http://www.ybadoo.com.br/
54. Desenvolver uma Gramática Livre do Contexto (GLC) que reconheça expressões matemáticas na notação
prefixada, considerando apenas os operadores de adição, subtração, multiplicação e divisão e que os
operandos sejam apenas números inteiros, números reais e variáveis. Uma variável é uma palavra
composta por dígitos e letras, cujo primeiro símbolo deve ser obrigatoriamente uma letra. A seguir são
apresentados algumas expressões válidas como exemplo.
+ a b
+ * 10 15 20
* + a b c
+ 10 * 20 30
55. Desenvolver uma Gramática Livre do Contexto (GLC) que reconheça expressões matemáticas na notação
pós-fixada, considerando apenas os operadores de adição, subtração, multiplicação e divisão e que os
operandos sejam apenas números inteiros, números reais e variáveis. Uma variável é uma palavra
composta por dígitos e letras, cujo primeiro símbolo deve ser obrigatoriamente uma letra. A seguir são
apresentados algumas expressões válidas como exemplo.
a b +
10 15 20 * +
a b c + *
10 20 + 30 *
56. Provar a ambiguidade da gramática:
G = ({S, A, B}, {a, b}, P, S)
P = { < S > → < A > < B > | a a < B >
 < A > → a | < A > a
 < B > → b }
57. Desenvolver uma Gramática Livre do Contexto (GLC) sobre o alfabeto {(, )}, que produza cadeias com
parênteses a esquerda e a direita, como por exemplo
(())
(()())
()()()
(()((())))
58. A gramática livre de contexto abaixo é uma descrição de um fragmento da língua inglesa. 
 
G = ({SENTENCE, NOUN-PHRASE, VERB-PHRASE, PREP-PHRASE, CMPLX-NOUN, CMPLX-VERB,
ARTICLE, NOUN, VERB, PREP}, {a, the, boy, girl, flower, touches, likes, sees,
with}, P, S)
P = { <SENTENCE> → <NOUN-PHRASE> <VERB-PHRASE> 
 <NOUN-PHRASE> → <CMPLX-NOUN> | <CMPLX-NOUN> <PREP-PHRASE> 
 <VERB-PHRASE> → <CMPLX-VERB> | <CMPLX-VERB><PREP-PHRASE> 
 <PREP-PHRASE> → <PREP> <CMPLX-NOUN> 
 <CMPLX-NOUN> → <ARTICLE> <NOUN> 
 <CMPLX-VERB> → <VERB> | <VERB> <NOUN-PHRASE> 
 <ARTICLE> → a | the 
 <NOUN> → boy | girl | flower 
 <VERB> → touches | likes | sees 
 <PREP> → with }
Apresente uma árvore de derivação da sentença a girl with a flower likes the boy.
6 de 8
Gramáticas Livre do Contexto
Linguagens Formais e Autômatos
http://www.ybadoo.com.br/
59. Apresente a derivação a extrema esquerda e a derivação a extrema direita da sentença a ( e , e , e )
sobre a gramática
G = ({S, Z, R, X, Y}, {a, e, (, ), ','}, P, S)
P = {< S > → < Z > )
 < Z > → < Z > , < X > | < R >
 < R > → < Y > ( < X >
 < X > → e
 < Y > → a }
60. Construa uma Gramática Livre do Contexto (GLC) sobre o alfabeto {0, 1, ..., 8, 9} que reconheça
exclusivamente os números arábicos pares. Exemplo de palavras que a gramática livre do contexto deve
reconhecer:
0
124
987345566
12345676898
61. Construa uma Gramática Livre do Contexto (GLC) que reconheça todas as expressões regulares possíveis
de serem construídas sobre o alfabeto {a, b, c}.
62. Apresente uma derivação à extrema esquerda da sentença ((a + b)*c + a) sobre a gramática
produzida no exercício 61.
63. Apresente uma derivação à extrema direita da sentença ((a + b)*c + a) sobre a gramática produzida
no exercício 61.
64. Apresente uma árvore de derivação da sentença a(a + b + c)*bc sobre a gramática produzida no
exercício 61.
G1 = ({atr, exp, id}, {A, B, C, :=, +, *, (, )}, P1, atr)
P1 = { <atr> → <id> := <exp>
<exp> → <id> + <exp> | <id> * <exp> | ( <exp> ) | <id>
<id> → A | B | C }
65. Modifique a gramática a seguir para adicionar um operador unitário que tenha uma precedência mais alta
do que a adição e a multiplicação.
G = ({atr, id, exp, ter, fat}, {A, B, C, :=, +, *, (, )}, P, atr)
P = { <atr> → <id> := <exp>
 <id> → A | B | C
 <exp> → <exp> + <ter> | <ter>
 <ter> → <ter> * <fat> | <fat>
 <fat> → ( <exp> ) | <id> }
66. Desenvolva uma gramática livre do contexto que gere a linguagem L = {0i 1j 2k | i = j ou j = k, com
i, j, k > 0}.
7 de 8
Gramáticas Livre do Contexto
Linguagens Formais e Autômatos
http://www.ybadoo.com.br/
67. Apresente a derivação a extrema esquerda e a derivação a extrema direita da sentença a(e, e, e)a
sobre a gramática a seguir
G = ({S, Z, R, X, Y}, {a, e, (, ), ','}, P, S)
P = { < S > → < Y > ( < Z >
 < Z > → < X > , < Z > | < R >
 < R > → < X > ) < Y >
 < X > → e
 < Y > → a }
68. Apresente a árvore de derivação (parse tree) da sentença 
a ( a + a ( a + a ) ) := a ( a + a ) + a ( a + a )
sobre a gramática a seguir:
G = ({S, E, V, I}, {a, (, ), +, :=}, P, S)
P = { < S > → < V > := < E > | < I > ( < E > )
 < E > → < E > + < V > | < V >
 < V > → < I > ( < E > ) | < I >
 < I > → a }
8 de 8