(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 G1 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).
G1 = ({E, T, F}, {a, +, *, (, )}, P1, E)
P1 = {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 G2 é necessário a aplicação de quantas produções?
G2 = ({A, B, C, D, E}, {w, x, y, z, =, +, -, *, /, (, )}, P2, A)
P2 = {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.
(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 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.
(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.
(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)*
(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 | ε}
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.
(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 {aibj | (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}
Uma gramática linear à direita é aquela em que todas as suas produções exibem as seguintes características:
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 → ε }
(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, ...
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 → AABS | ε
AB → BA
BA → AB
A → a
B → b}