Segunda Avaliação

Questão 01

(vale 1,0 ponto) Quando se consideram linguagens especificadas através de gramáticas livres de contexto, deve-se também considerar de que forma é feita a aceitação sintática de suas sentenças para fins de compilação e/ou interpretação. Quando se trata de efetuar o reconhecimento de sentenças, o que se busca, na verdade, é localizar uma sequência de produções que, quando aplicada à raiz da gramática, forneça como resultado, através da série correspondente de derivações, a sentença fornecida para análise. Sendo possível completar a derivação, diz-se que a sentença pertence à linguagem; caso contrário, que ela não pertence à linguagem.

Por exemplo, a derivação da sentença a + a sobre a gramática livre de contexto G₁ pode produzir a sequência de derivação E ⇒ T + E ⇒ F + E ⇒ F + T ⇒ a + T ⇒ a + F ⇒ a + a, no qual foram aplicadas seis produções, sendo elas (1), (4), (2), (6), (4), (6).

G₁ = ({E, T, F}, {a, +, *, (, )}, P₁, E)
P₁ = {E → T + E  (1)
     E → T      (2)
     T → F * T  (3)
     T → F      (4)
     F → ( E )  (5)
     F → A}     (6)

Conforme exposto, para o reconhecimento da sentença x = (y - z) / w + x sobre a gramática livre de contexto G₂ é necessário a aplicação de quantas produções?

G₂ = ({A, B, C, D, E}, {w, x, y, z, =, +, -, *, /, (, )}, P2, A)
P₂ = {A → E = B
     B → B + C | B - C | C
     C → C * D | C / D | D
     D → ( B ) | E
     E → w | x | y | z}

a. 19 produções.

b. 20 produções.

c. 21 produções.

d. 22 produções.

e. 23 produções.

Questão 02

(vale 1,0 ponto) Eventualmente, uma mesma palavra pode ser associada a duas ou mais árvores de derivação, determinando uma ambiguidade. Em muitas aplicações como, por exemplo, no desenvolvimento e otimização de alguns tipos de algoritmos de reconhecimento, é conveniente que a gramática usada não seja ambígua. Entretanto, nem sempre é possível eliminar ambiguidades. Na realidade, é fácil definir linguagens para as quais qualquer gramática livre de contexto é ambígua. Neste contexto, analise as afirmativas apresentadas a seguir:

A gramática G₁ = ({S}, {a, b}, {S → SS | a | b}, S) é ambígua para a entrada ba.
A gramática G₂ = ({S}, {a, b, +, *}, {S → SS+ | SS* | a | b}, S) é ambígua para a entrada aba+*.
A gramática G₃ = ({S}, {a, b, &, ^, (, )}, {S → S^S | S&S | (S) | a | b}, S) é ambígua para a entrada b^a&b.
A gramática G₄ = ({S}, {(, )}, {S → (S) | () | SS}, S) é ambígua para a entrada ()()().

A análise permite concluir que:

a. Apenas as afirmativas I e II estão corretas.

b. Apenas as afirmativas I e III estão corretas.

c. Apenas as afirmativas II e III estão corretas.

d. Apenas as afirmativas II e IV estão corretas.

e. Apenas as afirmativas III e IV estão corretas.

Questão 03

(vale 1,0 ponto) Conforme as restrições impostas ao formato das produções de uma gramática, a classe de linguagens que tal gramática gera varia correspondentemente. A teoria mostra que há quatro classes de gramáticas capazes de gerar quatro classes correspondentes de linguagens, de acordo com a denominada Hierarquia de Chomsky. Qual a classe mais restritiva que a gramática apresentada a seguir pode ser classificada.

G = ({S, X, Y}, {a, b}, P, S)
P = {S → Xa | Ya | Yb | ε
     X → Xa | Xb | ε
     Y → Sa | Sb}

a. Gramática regular à esquerda.

b. Gramática regular à direita.

c. Gramática livre de contexto.

d. Gramática sensível ao contexto.

e. Gramática irrestrita.

Questão 04

(vale 1,0 ponto) Uma linguagem regular é uma linguagem formal que pode ser expressa usando expressões regulares, ou seja, uma linguagem produzida utilizando as operações de concatenação, união e fecho de Kleene sobre os elementos de um alfabeto. De acordo com a hierarquia de Chomsky, linguagens regulares são aquelas geradas por gramáticas regulares. As linguagens regulares são utilizadas para descrever dispositivos que realizam computações simples, como os autômatos finitos, pois representam a linguagem mais elementar classificada pela hierarquia de Chomsky. Qual expressão regular expressa a linguagem regular gerada pela gramática regular apresentada a seguir?

G = ({S, X}, {a, b}, P, S)
P = {S → aX | bS | ε
     X → bS | ε}

a. ER = a(b + ab)*

b. ER = (b + ab)*a

c. ER = (b + ab)*(ε + a)

d. ER = (ab)*a

e. ER = (ε + a)(b + ab)*

Questão 05

(vale 1,0 ponto) Uma gramática livre de contexto é dita normalizada em relação a um certo padrão quando todas as suas produções seguem as restrições impostas pelo padrão em questão. É comum designar tais padrões como formas normais. Por exemplo, diz-se que uma gramática G = (V, Σ, P, S) obedece à Forma Normal de Chomsky se todas as produções p ∈ P forem de uma das duas formas seguintes:

A → BC, ou

A → a

Conforme exposto, converta a gramática livre de contexto apresentada a seguir na Forma Normal de Chomsky e analise as seguintes assertivas:

G = ({S, X, T}, {a, b, c, d}, P, S)
P = {S → XaXaS | XdT
     T → XaXaT | XaX
     X → Xb | Xc | ε}

Na simplificação da gramática, são aplicados os métodos de produções vazias e produções da forma A → B.
Na normalização dos terminais (A → a), são acrescentados 23 novas variáveis ao conjunto {S, X, T}.
Na normalização dos terminais (A → a), são acrescentados 26 novas variáveis ao conjunto {S, X, T}.
Na normalização das variáveis (A → BC), são acrescentados 18 novas variáveis ao conjunto {S, X, T}.

A análise permite concluir que:

a. Apenas as afirmativas I e II estão corretas.

b. Apenas as afirmativas I e III estão corretas.

c. Apenas as afirmativas II e III estão corretas.

d. Apenas as afirmativas II e IV estão corretas.

e. Apenas as afirmativas III e IV estão corretas.

Questão 06

(vale 1,0 ponto) Uma gramática G é livre de contexto se v é um único não terminal para toda produção v → w em P. Uma linguagem L sobre algum alfabeto terminal Σ é livre de contexto se pode ser gerada por uma gramática livre de contexto. Desenvolva uma gramática livre de contexto que gere a linguagem {aⁱb^j | (j = 2i) ou (j = 3i) e i > 0}.

Observação: a questão receberá a menção 1,0 caso esteja totalmente correta, caso contrário receberá a menção 0,0.

G = ({S, A, B}, {a, b}, P, S)
P = {S → A | B
     A → aAbb | abb
     B → aBbbb | abbb}

Questão 07

Uma gramática linear à direita é aquela em que todas as suas produções exibem as seguintes características:

α ∈ N
β ∈ Σ, β ∈ N, β ∈ ΣN ou β = ε, de forma não exclusiva.

Gramáticas lineares à direita também são conhecidas como gramáticas do tipo 3, e geram linguagens denominadas regulares, ou simplesmente do tipo 3. As linguagens regulares constituem a classe de linguagens mais simples dentro da Hierarquia de Chomsky, a qual prossegue com linguagens de complexidade crescente até as linguagens mais gerais, do tipo 0. Apresente uma gramática linear à direita sobre o alfabeto Σ = {x, y, z} que reconheça a linguagem L = {w | w possui yxx como prefixo, xyx ou xzy como subpalavra e yxz como sufixo}.

G = ({A, B, C, D, E, F, G, H, I, J, K, L}, {x, y, z}, P, A)
P = {A → yB
     B → xC
     C → xD | xE | xG
     D → yD | zD | xD | xE | xG
     E → yF
     F → xI | xK
     G → zH
     H → yI | yJ
     I → yI | zI | xI | yJ
     J → xK
     K → zL
     L → ε }

Questão Extra

(vale 1,0 ponto) Desenvolva uma gramática (regular, livre de contexto, sensível ao contexto ou irrestrita) que produza todas as palavras sobre o alfabeto {a, b}, tal que a quantidade de símbolos a's seja o dobro da quantidade de símbolos b's. Exemplo de palavras válidas: ε, aab, aba, baa, aaaabb, aaabab, aaabba, aabaab, aababa, aabbaa, abaaab, abaaba, ababaa, abbaaa, baaaab, baaaba, baabaa, babaaa, bbaaaa, ...