09. Hierarquia de Chomsky

pdfSlides


Exercícios Propostos

onExercício 09.01 Apresente uma derivação para a sentença aaabbbccc sobre a gramática G = ({S, B, C}, {a, b, c}, {< S > -> a < S > < B > < C > | a < B > < C >, < C > < B > -> < B > < C >, a < B > -> a b, b < B > -> b b, b < C > -> b c, c < C > -> c c}, S).

onExercício 09.02 Apresente uma derivação para a sentença bacbca sobre a gramática G = ({S, A, B, C}, {a, b, c}, {< S > -> < A > < B > < C > | < A > < B > < C > < S >, < A > < B > -> < B > < A >, < A > < C > -> < C > < A >, < B > < A > -> < A > < B >, < B > < C > -> < C > < B >, < C > < A > -> < A > < C >, < C > < B > -> < B > < C >, < A > -> a, < B > -> b, < C > -> c}, S).

onExercício 09.03 Apresente uma derivação para a sentença abbabb sobre a gramática G = ({S, A, B, T}, {a, b}, {< S > -> a < A > < S > | b < B > < S > | < T >, < A > a -> a < A >, < B > a -> a < B >, < A > b -> b < A >, < B > b -> b < B >, < A > < T > -> < T > a, < B > < T > -> < T > b, < T > -> ε}, S).

onExercício 09.04 Apresente uma derivação para a sentença aabbbccddd sobre a gramática G = ({S, A, B, X, Y}, {a, b, c, d}, {< S > -> < A > < B >, < A > -> a < A > < X > | a < X >, < B > -> b < B > d | b < Y > d, < X > b -> b < X >, < X > < Y > -> < Y > c, < Y > -> ε }, S).

onExercício 09.05 Apresente uma derivação para a sentença aabbbcccc sobre a gramática a G = ({S, A, B, C}, {a, b, c}, {< S > -> a < A > b < C > | a b < C >, < A > -> a < A > b < B > | < A > b < B > | < A > < B > | b < B > | < B >, < B > b -> b < B >, < B > < C > -> < C > c, < C > -> c }, S).

onExercício 09.06 Apresente uma derivação para a sentença bbabbbab sobre a gramática G = ({S, A, B, T}, {a, b}, {< S > -> a < A > < S > | b < B > < S > | < T >, < A > a -> a < A >, < B > a -> a < B >, < A > b -> b < A >, < B > b -> b < B >, < A > < T > -> < T > a, < B > < T > -> < T > b, < T > -> ε}, S).

onExercício 09.07 Desenvolva uma gramática linear à esquerda sobre o alfabeto Σ = {a, b, c} que reconheça a linguagem L = {w | w possui ab como prefixo, bc como subpalavra e ca como sufixo}.

onExercício 09.08 Desenvolva uma gramática linear à direita sobre o alfabeto Σ = {a, b, c} que reconheça a linguagem L = {w | w possui ab como prefixo, bc como subpalavra e ca como sufixo}.

onExercício 09.09 Apresente uma derivação para a sentença aaabbbbbbaaa sobre a gramática irrestrita a seguir.

onExercício 09.10 Apresente uma derivação para a sentença aaabbbaaabbb sobre a gramática irrestrita a seguir.

onExercício 09.11 Apresente uma derivação para a sentença aaaaaaaa sobre a gramática irrestrita a seguir.

onExercício 09.12 Apresente uma derivação para a sentença aaabbbaaa sobre a gramática sensível ao contexto a seguir.

onExercício 09.13 Apresente uma derivação para a sentença aaabbbbbbaaa sobre a gramática sensível ao contexto a seguir.

onExercício 09.14 Apresente uma derivação para a sentença aaabbbaaabbb sobre a gramática sensível ao contexto a seguir.

onExercício 09.15 Desenvolva uma gramática linear à esquerda sobre o alfabeto Σ = {a, b, c} que reconheça a linguagem L = {w | w possui cbb como prefixo, bac como subpalavra e cac como sufixo}.

onExercício 09.16 Desenvolva uma gramática linear à direita sobre o alfabeto Σ = {a, b, c} que reconheça a linguagem L = {w | w possui cbb como prefixo, bac como subpalavra e cac como sufixo}.

onExercício 09.17 Desenvolva uma gramática linear à esquerda sobre o alfabeto Σ = {a, b, c} que reconheça a linguagem L = {w | w possui cbc como prefixo, cba como subpalavra e bab como sufixo}.

onExercício 09.18 Desenvolva uma gramática linear à direita sobre o alfabeto Σ = {a, b, c} que reconheça a linguagem L = {w | w possui cbc como prefixo, cba como subpalavra e bab como sufixo}.

onExercício 09.19 Desenvolva uma gramática linear à esquerda sobre o alfabeto Σ = {a, b, c} que reconheça a linguagem L = {w | w possui bac como prefixo, acb como subpalavra e bca como sufixo}.

onExercício 09.20 Desenvolva uma gramática linear à direita sobre o alfabeto Σ = {a, b, c} que reconheça a linguagem L = {w | w possui bac como prefixo, acb como subpalavra e bca como sufixo}.

onExercício 09.21 Desenvolva uma gramática linear à esquerda sobre o alfabeto Σ = {a, b, c} que reconheça a linguagem L = {w | w possui bca como prefixo, cab como subpalavra e bbb como sufixo}.

onExercício 09.22 Desenvolva uma gramática linear à direita sobre o alfabeto Σ = {a, b, c} que reconheça a linguagem L = {w | w possui bca como prefixo, cab como subpalavra e bbb como sufixo}.

onExercício 09.23 Desenvolva uma gramática linear à esquerda sobre o alfabeto Σ = {a, b, c} que reconheça a linguagem L = {w | w possui acc como prefixo, cab como subpalavra e abc como sufixo}.

onExercício 09.24 Desenvolva uma gramática linear à direita sobre o alfabeto Σ = {a, b, c} que reconheça a linguagem L = {w | w possui acc como prefixo, cab como subpalavra e abc como sufixo}.

onExercício 09.25 Desenvolva uma gramática linear à esquerda sobre o alfabeto Σ = {x, y, z} que reconheça a linguagem L = {w | w possui zyz como prefixo, yzx como subpalavra e xzx como sufixo}.

onExercício 09.26 Desenvolva uma gramática linear à direita sobre o alfabeto Σ = {x, y, z} que reconheça a linguagem L = {w | w possui zyz como prefixo, yzx como subpalavra e xzx como sufixo}.

onExercício 09.27 Desenvolva uma gramática linear à esquerda sobre o alfabeto Σ = {x, y, z} que reconheça a linguagem L = {w | w possui xxy ou zyy como prefixo, xyx ou yzx como subpalavra e xxz ou zxy como sufixo}.

onExercício 09.28 Desenvolva uma gramática linear à direita sobre o alfabeto Σ = {x, y, z} que reconheça a linguagem L = {w | w possui xxy ou zyy como prefixo, xyx ou yzx como subpalavra e xxz ou zxy como sufixo}.

onExercício 09.29 Apresente uma derivação para a sentença abbcabbc sobre a gramática irrestrita a seguir.


Recomendamos

Revista Tema Kinghost Clickarvore