Turmas - 2º Semestre de 2024Quando 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 = w * (y + z) - 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. 17 produções.
b. 18 produções.
c. 19 produções.
d. 20 produções.
e. 21 produções.
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.
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 → aX | aY | bY | ε
X → aX | bX | ε
Y → aS | bS}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.
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 → aS | bS | X
X → cX | Y
Y → dY | eY | ε}a. ER = (a + b)*c*(d + e)*
b. ER = (a + b + c)*(d + e)*
c. ER = (a + b)*c(d + e)*
d. ER = (e + d)*c*(b + a)*
e. ER = (e + d)*(c + b + a)*
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, W, A, B}, {a, b}, P, S)
P = {S → AW | WB
W → aWb | ε
A → aA | a
B → bB | b}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.
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}.
G = ({S, A, B}, {a, b}, P, S)
P = {S → A | B
A → aAbb | ε
B → aBbbb | ε}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 Σ = {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 → aB
B → bC
C → cD | cF | cG
D → aD | bD | cD | bE | cG
E → cF
F → aI | aK
G → aH
H → cI | cJ
I → aI | bI | cI | cJ
J → aK
K → bL
L → ε }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 uma unidade a mais do que de símbolos b's. Exemplo de palavras válidas: a, aab, aba, baa, aaabb, aabab, aabba, abaab, ababa, abbaa, baaab, baaba, babaa, bbaaa, aaaabbb, ...
G = ({S, A, B}, {a, b}, P, S)
P = {S → ABS | A
AB → BA
BA → AB
A → a
B → b}Ybadoo - Soluções em Software Livre • Copyright 2009/2025 • 