Segunda Avaliação

Questão 01

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 = w * (z + x / y) 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 → C + B | C - B | C
     C → D * C | D / C | D
     D → ( B ) | E
     E → w | x | y | z}

a. 17 produções.

b. 18 produções.

c. 19 produções.

d. 20 produções.

e. 21 produções.

Questão 02

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 aabaa.
A gramática G₂ = ({S}, {a, b, &, ^, (, )}, {S → S^S | S&S | (S) | a | b}, S) é ambígua para a entrada (a^b)&a^b.
A gramática G₃ = ({S}, {(, )}, {S → (S) | () | SS}, S) é ambígua para a entrada (()()).
A gramática G₄ = ({S}, {a, b, +, *}, {S → +SS | *SS | a | b}, S) é ambígua para a entrada +*aba.

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

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}, {a, b}, P, S)
P = {S → XY | YX
     X → AX | A
     Y → BY | B
     AA → aa
     BB → b}

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

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, Y}, {a, b, c, d, e}, P, S)
P = {S → Sd | Se | X
     X → Yc
     Y → Ya | Yb | ε}

a. ER = (a + b)*c(d + e)*

b. ER = (e + d)*c(b + a)*

c. ER = (a + b + c)*(d + e)*

d. ER = (e + d)*c*(b + a)*

e. ER = (e + d)*(c + b + a)*

Questão 05

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, A, B, C, D}, {a, b, c, d}, P, S)
P = {S → ABCD
     A → aA | ε
     B → bB | ε
     C → cC | c
     D → dD | dd}

Na simplificação da gramática, é aplicado somente o método de produções vazias.
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 6 novas variáveis ao conjunto {S, A, B, C, D}.
Na normalização das variáveis (A → BC), são acrescentados 6 novas variáveis ao conjunto {S, A, B, C, D}.

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

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 | (i = 2j) ou (i = 3j) e j ≥ 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 → aaAb | ε
     B → aaaBb | ε}

Questão 07

Uma gramática linear à esquerda é 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 à esquerda 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 à esquerda sobre o alfabeto Σ = {a, b, c} que reconheça a linguagem L = {w | w possui abc como prefixo, bca ou cac como subpalavra e cab como sufixo}.

G = ({A, B, C, D, E, F, G, H, I, J, K, L}, {x, y, z}, P, A)
P = {A → Bb
     B → Ca | Ea
     C → Dc | Gc
     D → Da | Db | Dc | Ea | Gc
     E → Fc | Jc
     F → Ib
     G → Ha
     H → Ic | Jc
     I → Ia | Ib | Ic | Jc
     J → Kb
     K → La
     L → ε }

Questão Extra

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 b's seja o triplo da quantidade de símbolos a's. Exemplo de palavras válidas: ε, abbb, babb, bbab, bbba, aabbbbbb, ababbbbb, abbabbbb, abbbabbb, abbbbabb, abbbbbab, abbbbbba, baabbbbb, bababbbb, babbabbb, babbbabb, babbbbab, babbbbba, ...