SlidesExercícios Propostos
Exercício 08.01 Simplifique por meio do algoritmo de Exclusão de Produções Vazias a gramática G = ({S, A, B}, {a, b}, {< S > -> < A > < B > | a < B > < B > | a < S > < B > a, < A > -> a | a < B > | a < S > b, < B > -> ε | b < B > | a < S > < B >}, S).
Exercício 08.02 Simplifique por meio do algoritmo de Exclusão de Produções Vazias a gramática G = ({S, X, Y, Z, W}, {a, b, c}, {< S > -> a < X > b | < X > < Y > | < W > a, < X > -> ε | < Y > < X > a, < Y > -> < W > a | < Z > a c, < Z > -> < S > < Y > a | < W > b < Z > | < X >, < W > -> a < X > c | < Z >}, S).
Exercício 08.03 Simplifique por meio do algoritmo de Exclusão de Produções Vazias a gramática G = ({A, B, C, D, E, F}, {x, y, z}, {< A > -> x < D > < B > | < F > < C >, < B > -> y < A > < F > | < F > < D >, < C > -> y < D > x, < D > -> < A > < B > < F > | ε, < E > -> x < B > y < D > z < F > | x < A > < B >, < F > -> x y < B > < A > | < D >}, A).
Exercício 08.04 Simplifique por meio do algoritmo de Exclusão de Produções Vazias a gramática G = ({S, A, B, C, D, E, F}, {a, b, c, d, e, f}, {< S > -> a < A > a | < A >, < A > -> < B > | c < C > < D > d, < B > -> b < S > b b | b | ε, < C > -> a a < A > a a | < S >, < D > -> < C > < D > d | d < D >, < E > -> < F > f | < S > f < A > e, < F > -> e < E > e | f | < B > c d < C > < D >}, S).
Exercício 08.05 Simplifique por meio do algoritmo de Exclusão de Produções Vazias a gramática G = ({A, B, C, D, E, F, G, H}, {x, y, z}, {< A > -> < F > | z < B > < C >, < B > -> < G > x | y < A > < D > z, < C > -> < A > < D > | y z | < B > < H >, < D > -> < C > x y | ε | < A > z, < E > -> < C > < D > < A > | y, < F > -> < D > | < A > x < C > < D > y < A >, < G > -> < E > < A > | x y < E >, < H > -> < A > y < C > | < D > < C > z}, A).
Exercício 08.06 Simplifique por meio do algoritmo de Exclusão de Produções da Forma < A > -> < B > a gramática G = ({A, B, C, D, E}, {x, y, z}, {< A > -> x < A > y | < C > | y y, < B > -> x | < E > | y, < C > -> < D > | < B > x | < D > < E >, < D > -> z < E > | z | x < A >, < E > -> < A > < B > | y}, A).
Exercício 08.07 Simplifique por meio do algoritmo de Exclusão de Produções da Forma < A > -> < B > a gramática G = ({A, B, C, D, E}, {x, y, z}, {< A > -> x < B > y | z < C > < D > | < E >, < B > -> < D > | x < A >, < C > -> x y | < A > < B >, < D > -> < D > x < E > | < C >, < E > -> x | < C > | < B > < C > z}, A).
Exercício 08.08 Simplifique por meio do algoritmo de Exclusão de Produções da Forma < A > -> < B > a gramática G = ({A, B, C, D, E, F}, {x, y, z}, {< A > -> x < B > y | < C >, < B > -> z < C > x | < C > < D >, < C > -> < E > | x < A > | < F >, < D > -> < E > < F > | < A > x y, < E > -> x y z | < B >, < F > -> < D > | x < B > < C >}, A).
Exercício 08.09 Simplifique por meio do algoritmo de Exclusão de Produções da Forma < A > -> < B > a gramática G = ({A, B, C, D, E, F, G}, {x, y, z}, {< A > -> x < D > | < E >, < B > -> < F > | y, < C > -> y x | < A > z, < D > -> < G > | x < A >, < E > -> x | < C >, < F > -> < D > | x < A > y, < G > -> < C > x | < C >}, A).
Exercício 08.10 Simplifique por meio do algoritmo de Exclusão de Símbolos Inúteis a gramática G = ({S, A, B, C, D}, {0, 1}, {< S > ::= 0 < S > 1 | 0 < A > | 0 1 < C >, < A > ::= < A > < S > < C > | 1 < C > | 1, < B > ::= 0 < B > 1 | 0 1, < C > ::= 0 < D > 1, < D > ::= 0 1 < C > }, S).
Exercício 08.11 Simplifique por meio do algoritmo de Exclusão de Símbolos Inúteis a gramática G = ({A, B, C, D, E, F, G}, {x, y, z}, {< A > -> x < F > y | < B > x < E >, < B > -> x < G > | < G > y, < C > -> y | y < G >, < D > -> z < C > | z z < B >, < E > -> y | < F > x, < F > -> < G > y | < E > x x, < G > -> < B > z < B >}, A).
Exercício 08.12 Simplifique por meio do algoritmo de Exclusão de Símbolos Inúteis a gramática G = ({S, A, B, C, D, F, H}, {a, b, c, d}, {< S > -> < A > < C > < H > | < B > < B >, < A > -> a < A > | a < F >, < B > -> < C > < F > < H > | b, < C > -> a < C > | < D > < H >, < D > -> a < D > | < B > < D > | < C > a, < F > -> b < B > | b, < H > -> d < H > | d}, S).
Exercício 08.13 Simplifique por meio do algoritmo de Exclusão de Símbolos Inúteis a gramática G = ({S, K, Q, R, T, U, W}, {a, b, c, d, e}, {< S > -> a < K > b < Q > | c d < R > | < U >, < K > -> < Q > c | < K >, < Q > -> d < K > | c < Q > d c, < R > -> a b < U > < T > d | < U > a b c | a c < T > e, < T > -> < T > a c | c < T > a | a c d, < U > -> a < Q > b < K > c, < W > -> < R > < R > c}, S).
Exercício 08.14 Simplifique por meio do algoritmo de Exclusão de Símbolos Inúteis a gramática G = ({X, Y, Z, K, W, T, R, S}, {a, b, c}, {< X > -> < K > a < T > | < S > < Z >, < Y > -> c < R > < S > | < W > c, < Z > -> a b | < R > c < K >, < K > -> < K > b | < R > c, < W > -> < Z > < X > | c < K > b < X >, < T > -> c | < K > < W > b, < R > -> b < K > < X > | c < K > b, < S > -> < Z > a | b < Z >}, X).
Exercício 08.15 Simplifique por meio do algoritmo de Exclusão de Símbolos Inúteis a gramática G = ({S, R, X, Z, W, Y, K, T}, {a, b, c}, {< S > -> < W > b | b < T >, < R > -> < X > b b < A > | < Y > a < Z > b, < X > -> < K > c | a < W > b, < Z > -> c | < A > b | c < W > b, < W > -> a b < X > | < K > < A > c, < Y > -> < A > < Z > c | < K > a < X >, < K > -> < X > < R > | < W > < A >, < T > -> < S > | < T > a | < K > < X > | a}, S).
Exercício 08.16 Converta para a Forma Normal de Chomsky a gramática G = ({S, A, B}, {a, b}, {< S > -> < A > < A > < A > | < B >, < A > -> a < A > | < B >, < B > -> ε}, S).
Exercício 08.17 Converta para a Forma Normal de Chomsky a gramática G = ({S, A, B}, {a, b}, {< S > -> a < A > < B >, < A > -> b < B > b, < B > -> < A > | ε}, S).
Exercício 08.18 Converta para a Forma Normal de Chomsky a gramática G = ({S, A, B}, {a, b}, {< S > -> a b < A > < B >, < A > -> b < A > < B > | ε, < B > -> < B > < A > a | < A >}, S).
Exercício 08.19 Converta para a Forma Normal de Chomsky a gramática G = ({S, A, B}, {a, b}, {< S > -> < A > < S > < B > | ε, < A > -> a < A > < S > | a, < B > -> < S > b < S > | < A > | b b}, S).
Exercício 08.20 Converta para a Forma Normal de Chomsky a gramática G = ({S, A, B}, {a, b}, {< S > -> b < A > | a < B >, < A > -> b < A > < A > | a < S > | a, < B > -> a < B > < B > | b < S > | b}, S).
Exercício 08.21 Converta para a Forma Normal de Chomsky a gramática G = ({S, T, L}, {a, b, +, -, *, /, [, ]}, {< S > -> < T > + < S > | < T > - < S > | < T >, < T > -> < L > * < T > | < L > / < T > | < L >, < L > -> a | b | [ < S > ]}, S).
Exercício 08.22 Converta para a Forma Normal de Chomsky a gramática G = ({S, A, B, C}, {a, b}, {< S > -> < A > < B > | < C > < A >, < A > -> a, < B > -> < B > < C > | < A > < B >, < C > -> a < B > | b}, S).
Exercício 08.23 Converta para a Forma Normal de Chomsky a gramática G = ({A, B, C, D}, {x, y, z}, {< A > -> < C > x < D >, < B > -> y | < A > x, < C > -> z z | z < A > z, < D > -> y < B > | < B > x}, A).
Exercício 08.24 Converta para a Forma Normal de Chomsky a gramática G = ({S, A, B, C, D}, {a, b}, {< S > -> a < A > a | b < B > b | ε, < A > -> < C > | a, < B > -> < C > | b, < C > -> < C > < D > < E > | ε, < D > -> < A > | < B > | a b}, S).
Exercício 08.25 Converta para a Forma Normal de Chomsky a gramática G = ({A, B, C, D, E, F}, {x, y, z}, {< A > -> < B > x y | z < F > y, < B > -> < C > < D > z | y < A >, < C > -> < F > x < D > | ε, < D > -> x < B > < C > | < C >, < E > -> z | < F > x, < F > -> < A > z | < E >}, A).
Exercício 08.26 Converta para a Forma Normal de Chomsky a gramática G = ({X, Y, Z, K, W, T}, {a, b, c}, {< X > -> < K > < W > | a < K >, < Y > -> ε | < X > < W > b, < Z > -> < X > < K > | < Y > | c < K >, < K > -> b | < X > < W > a, < W > -> < Y > | < X > b < Y >, < T > -> c < Z > < Y > | < Y > b < Z >}, X).
Exercício 08.27 Converta para a Forma Normal de Chomsky a gramática G = ({S, X, Y, A, B, Z}, {a, b, c, d}, {< S > -> < X > < Y > < Z >, < X > -> < A > < X > < A > | < B > < X > < B > | < Z >, < Y > -> < A > < Y > < B > | < B > < Y > < A > | < Z >, < A > -> a, < B > -> b, < Z > -> < Z > c | < Z > d | ε}, S).
Exercício 08.28 Converta para a Forma Normal de Chomsky a gramática G = ({A, B, C, D, E, F}, {a, b, c, +, *, (, )}, {< A > -> < C > < B >, < B > -> + < C > < B > | ε, < C > -> < E > < D >, < D > -> * < E > < D > | ε, < E > -> ( < A > ) | < F >, < F > -> a | b | c}, A).
Exercício 08.29 Converta para a Forma Normal de Chomsky a gramática G = ({S, A, B, C, D, E, F}, {a, b, c, d}, {< S > -> a < A > b < B > | c d < C > | < E >, < A > -> < A > | < B > c, < B > -> d < A > | c < B > d c, < C > -> a b < E > < D > d | < E > a b c | a c < D > b, < D > -> < D > a c | c < D > a | a c d, < E > -> a < B > b < A > c | ε, < F > -> < C > < C > c}, S).
Exercício 08.30 Converta para a Forma Normal de Chomsky a Gramática Livre do Contexto (GLC) da linguagem de programação SIMPLE (Deitel, 2003).
Exercício 08.31 Simplifique por meio do algoritmo de Exclusão de Produções da Forma < A > -> < B > a gramática G = ({A, B, C, D, E, F, G}, {x, y, z}, {< A > -> y < B > z | < C >, < B > -> z | < A > y < E > | < D >, < C > -> < E > | < B > x | y, < D > -> < E > < F > | x < G >, < E > -> z z | y < G >, < F > -> z < G > | < G > z | < G >, < G > -> < F > < F > | < B >}, A).
Exercício 08.32 Simplifique por meio do algoritmo de Exclusão de Produções Vazias a gramática G = ({A, B, C, D, E, F}, {x, y, z}, {< A > -> < B > x | < C > < F >, < B > -> < F > x < A > | y z < C >, < C > -> < B > z < A > | ε, < D > -> y | < E > < F >, < E > -> < A > x y | < F > x < A > y < D >, < F > -> < C > | < C > < D >}, A).
Exercício 08.33 Simplifique por meio do algoritmo de Exclusão de Produções da Forma < A > -> < B > a gramática G = ({A, B, C, D, E}, {x, y, z}, {< A > -> < E > | x y < A >, < B > -> z | < A > < C >, < C > -> < D > | x | < E >, < D > -> z < A > | z, < E > -> < A > < B > | < B >}, A).
Exercício 08.34 Converta para a Forma Normal de Greibach a gramática G = ({E, T, F}, {a, +, *, (, )}, {< E > -> < E > + < T > | < T > * < F > | ( < E > ) | a, < T > -> < T > * < F > | ( < E > ) | a, < F > -> ( < E > ) | a}, E).
Exercício 08.35 Converta para a Forma Normal de Greibach a gramática G = ({S, A, B, C}, {a, b}, {< S > -> < A > < B > | < B > < C >, < A > -> < A > < B > | a, < B > -> < A > < A > | < C > < B > | a, < C > -> a | b}, S).
Exercício 08.36 Converta para a Forma Normal de Greibach a gramática G = ({S, A, B, C}, {a, b, c}, {< S > -> < A > < B >, < A > -> < A > < B > | < C > < B > | a, < B > -> < A > < B > | b, < C > -> < A > < C > | c}, S).
Exercício 08.37 Converta para a Forma Normal de Greibach a gramática G = ({S, A, B, C}, {a, b}, {< S > -> < C > < A > | < A > < C > | a, < A > -> < B > < A > | < A > < B > | b, < B > -> < A > < A > | a | b, < C > -> < A > < C > | < C > < C > | a}, S).
Exercício 08.38 Converta para a Forma Normal de Greibach a gramática G = ({S, A, B, C}, {a, b}, {< S > -> < B > < B > | < B > < C > | b, < A > -> < A > < C > | < C > < A > | a, < B > -> < B > < B > | a, < C > -> < B > < C > | < C > < A > | a}, S).
Exercício 08.39 Converta para a Forma Normal de Greibach a gramática G = ({S, A, B, C}, {a, b}, {< S > -> < S > < C > | < A > < A > | a, < A > -> < C > < A > | < A > < B > | a, < B > -> < A > < C > | b, < C > -> < C > < A > | < A > < S > | b}, S).
Exercício 08.40 Converta para a Forma Normal de Chomsky a gramática G = ({S, A, B, C}, {a, b, c}, {< S > -> < A > < B > < C > | < C > < B > < A >, < A > -> a, < B > -> < B > a < C > | < A > < C > c, < C > -> a < B > | b}, S).
Exercício 08.41 Converta para a Forma Normal de Greibach a gramática G = ({S, A, B, C}, {a, b, c}, {< S > -> < A > < B > c, < A > -> < B > < A > | < C > c < B > | a, < B > -> < A > < B > b | b, < C > -> < C > < A > | c}, S).
Exercício 08.42 Converta para a Forma Normal de Chomsky a gramática G = ({A, B, C, D, E, F}, {x, y, z}, {< A > -> < E > x y | z < D >, < B > -> < D > < F > | x < C > y, < C > -> x < E > < B > | < F > < C > z, < D > -> y < C > < A > | < A > < F > < A > | ε, < E > -> < A > z < C > | < B > < E > y z, < F > -> z < A > y | < D > | < A > < C > < B >}, A).
Exercício 08.43 Simplifique por meio do algoritmo de Exclusão de Produções Vazias e por meio do algoritmo de Exclusão de Produções da Forma < A > -> < B > a gramática: G = ({A, B, C, D, E, F}, {w, x, y, z}, {< A > -> < B > < D > w | < C > < F >, < B > -> < F > < A > y | < D > < F >, < C > -> y z < D >, < D > -> < B > < F > < A > | ε, < E > -> w < F > y x < B > < D > | < A > x < B >, < F > -> x < B > < A > y | < D > }, A).
Exercício 08.44 Simplifique a gramática G = ({S, A, B, C, D, E, F}, {w, x, y, z}, {< S > -> < A > x < C > y | < C > | z < B > < A > w, < A > -> < E > < S > w | z < A > y < C > | x, < B > -> < C > w < E > | < E > x y | < B > < F > < A >, < C > -> y < A > x y | ε | < B > < D > w, < D > -> < S > y z < A > | x | w < E > y, < E > -> < F > x z < B > | < D > < S > < E >, < F > -> < D > y | < C > < S > | < S > < B > z}, S).
Exercício 08.45 Simplifique por meio do algoritmo de Exclusão de Produções Vazias a gramática: G = ({A, B, C, D, E}, {x, y, z}, {< A > -> < B > x < C > < D > | x y | < A > < B > < D >, < B > -> < E > < E > | < E > z < D > | z z, < C > -> x y < B > < D > | < B > < D > | z < B > z < C >, < D > -> < A > < B > < C > | < E > | x y, < E > -> < B > y < D > | x < B > y < C > | ε}, A).
Exercício 08.46 Simplifique por meio do algoritmo de Exclusão de Produções da Forma < A > -> < B > a gramática: G = ({A, B, C, D, E}, {x, y, z}, {< A > -> < A > < B > < C > | < D > | z, < B > -> < C > | x | < D >, < C > -> z y | < C > z | < C > y, < D > -> < A > < B > < C > | < E > | x y, < E > -> < B > y < D > | x < B > y < C > | x y}, A).
Exercício 08.47 Simplifique por meio do algoritmo de Exclusão de Símbolos Inúteis a gramática: G = ({A, B, C, D, E}, {x, y, z}, {< A > -> < A > < B > < C > | x < D > x | y < C > y, < B > -> x y < C > | x < B > z | < B > < C >, < C > -> < B > x | y < C > z | x < B > < C >, < D > -> < C > x y | < E > < E > | < E > < C > x, < E > -> x | < B > y | < A > z}, A).
Exercício 08.48 Converta para a Forma Normal de Chomsky a gramática: G = ({A, B, C, D, E, F, G, H}, {w, x, y, z, +, -, *, /, %, ^, (, )}, {< A > -> < C > < B >, < B > -> + < C > < B > | - < C > < B > | ε, < C > -> < E > < D >, < D > -> * < E > < D > | / < E > < D > | % < E > < D > | ε, < E > -> < G > < F >, < F > -> ^ < G > < F > | ε, < G > -> ( < A > ) | < H >, < H > -> w | x | y | z }, A).
Exercício 08.49 Converta para a Forma Normal de Greibach a gramática: G = ({S, A, B, C}, {a, b, c}, {< S > -> < B > < A >, < A > -> < A > < A > < C > | a, < B > -> < A > < A > < B > | < C > b, < C > -> < S > < C > | c }, S).
Exercício 08.50 Simplifique por meio do algoritmo de Exclusão de Produções Vazias a gramática G = ({A, B, C, D, E, F, G, H}, {w, x, y, z}, {< A > -> < F > | z < B > < C >, < B > -> < G > x | < A > w < D > z, < C > -> < D > < A > | w z | < H > < B >, < D > -> x < C > y | < F > | z < A >, < E > -> < C > < D > < A > | y, < F > -> ε | < A > x < C > < D > y < A >, < G > -> < E > w < A > | x y < E >, < H > -> < C > x < A > | < D > < C > z}, A).
Exercício 08.51 Simplifique por meio do algoritmo de Exclusão de Produções da Forma < A > -> < B > a gramática G = ({A, B, C, D, E, F, G}, {w, x, y, z}, {< A > -> x < D > y | < E >, < B > -> < F > | w, < C > -> y x w | < E >, < D > -> < G > | x < A > w, < E > -> x | < A > z, < F > -> < D > | x y < A >, < G > -> w < C > x | < C > }, A).
Exercício 08.52 Simplifique por meio do algoritmo de Exclusão de Símbolos Inúteis a gramática G = ({X, Y, Z, K, W, T, R, S}, {a, b, c, d}, {< X > -> a < K > < T > | < Z > < X >, < Y > -> < R > d < S > | a < W >, < Z > -> a b c | < R > d < K >, < K > -> a < K > b | d < R > c, < W > -> < Z > < X > | < K > c b < X >, < T > -> d | < K > < W > b, < R > -> < K > < X > c | d b, < S > -> a < Z > | b < Z > | c < Z > | d < Z > }, X).
Exercício 08.53 Converta para a Forma Normal de Chomsky a gramática G = ({A, B, C, D, E, F, G}, {w, x, y, z}, {< A > -> x < C > < D > z | < D > | < F > < B > x < G >, < B > -> < F > x < G > | < D > x < F > | < C > < E >, < C > -> x < A > z | < E > | < D > z, < D > -> x < E > | w < F > z, < E > -> < E > < F > < D > | < D > < F > | < F > x | ε, < F > -> y < F > x | x < F > < F > w | w z < F >, < G > -> < B > < C > | < A > < B > < C > | w < A > y }, A).
Exercício 08.54 Converta para a Forma Normal de Greibach a gramática G = ({A, B, C, D}, {x, y, z}, {< A > -> < D > x < D >, < B > -> y | < A > x, < C > -> z z | z < A > z, < D > -> y < B > | < B > x }, A).
Exercício 08.55 Simplifique por meio do algoritmo de Exclusão de Produções Vazias a gramática G = ({A, B, C}, {x, y}, { < A > ::= x < B > | y < C > < C > | x < A > < C > y, < B > ::= y | < C > x | < C > < C >, < C > ::= ε | y < C > | x < B > < C > }, A).
Exercício 08.56 Simplifique por meio do algoritmo de Exclusão de Produções da Forma < A > -> < B > a gramática G = ({A, B, C, D, E}, {x, y, z}, { < A > ::= x y < A > | < B > | x y < C >, < B > ::= x | < E > | y, < C > ::= < D > | < B > x | < D > < E >, < D > ::= < E > z | z z | < A > x, < E > ::= < B > < A > | y | < D > z }, A).
Exercício 08.57 Converta para a Forma Normal de Greibach a gramática G = ({S, X, K, Y}, {x, y, z}, {< S > -> < K > < Y > | < X > < K >, < X > -> < X > < K > | x, < K > -> < Y > < K > | < X > < X > | x, < Y > -> y | z}, S).
Exercício 08.58 Simplifique por meio do algoritmo de Exclusão de Produções Vazias a gramática: G = ({A, B, C, D, E, F, G}, {w, x, y, z}, {< A > -> < F > | z < D > < G >, < B > -> < F > x | < B > w < C > z, < C > -> < A > < D > | x z | < B > < E >, < D > -> x < D > y | < F > | z < F >, < E > -> < A > < C > < D > | y, < F > -> ε | x < A > < D > y < A >, < G > -> < A > w < E > | x < F > y}, A).
Exercício 08.59 Simplifique por meio do algoritmo de Exclusão de Produções da Forma < A > -> < B > a gramática: G = ({A, B, C, D, E, F, G}, {w, x, y, z}, {< A > -> x < D > y | < E >, < B > -> x < F > y | w, < C > -> y x w | < B >, < D > -> < G > | x < A > w, < E > -> x | < A > z, < F > -> < D > | x y < A >, < G > -> w < C > x | < A >}, A).
Exercício 08.60 Simplifique por meio do algoritmo de Exclusão de Símbolos Inúteis a gramática: G = ({X, Y, Z, K, W, T, R, S}, {a, b, c, d}, {< X > -> a < K > < T > | < Z > < S >, < Y > -> < R > d < S > | a < W >, < Z > -> a b c | < R > d < K >, < K > -> a < K > b | d < R > c, < W > -> < Z > < X > | < K > c b < X >, < T > -> d | < K > < W > b, < R > -> < K > < R > c | d b < R >, < S > -> a < Z > | b < Z > | c < Z >}, X).