Turmas - 2º Semestre de 2018(Menezes, 2000) A classe das linguagens livres de contexto, ou tipo 2, contém propriamente a classe das linguagens regulares, ou tipo 3, sendo de fundamental importância na ciência da computação, pois compreende um universo mais amplo de linguagens (comparativamente com as regulares) tratando, adequadamente, questões como parênteses balanceados, construções bloco-estruturadas, entre outras, típicas de linguagens de programação como Pascal, C e Algol. Analise as seguintes linguagens livres de contexto.
{S → aaaS | aaa}{S → BC, B → aBb | ab, C → cC | c}{S → XY, X → aXb | ε, Y → cYd | ε}É correto apenas o que se afirma na(s) assertiva(s):
a. I.
b. II.
c. III.
d. I e II.
e. I e III.
(Aho, 2008) Para a maioria dos analisadores sintáticos, é desejável que a gramática livre de contexto não seja ambígua, pois do contrário, não será possível determinar univocamente qual árvore de derivação deverá ser selecionada para uma dada sentença. Se uma gramática livre de contexto G é considerada ambígua, então:
a. Todas as sentenças de L(G) possuem duas ou mais derivações mais à esquerda diferentes.
b. Todas as sentenças de L(G) possuem duas ou mais derivações mais à direita diferentes.
c. Todas as sentenças de L(G) possuem duas ou mais árvores de sintaxe diferentes.
d. Existe pelo menos uma sentença pertencente à L(G) com duas derivações mais à esquerda diferentes.
e. Todas as sentenças de L(G) possuem pelo menos uma derivação mais à direita.
(Ramos, 2009) O principal mérito da Hierarquia de Chomsky foi agrupar as linguagens em classes, de tal forma que elas possam ser hierarquizadas de acordo com a sua complexidade relativa. Como resultado, é possível antecipar as propriedades fundamentais exibidas por uma determinada linguagem, ou mesmo vislumbrar os modelos de implementação mais adequados à sua realização, conforme a classe a que pertença. Se uma linguagem L é dita regular, ou tipo 3, então:
a. Existe uma gramática linear à direita que gera L, mas pode ser que não exista nenhum autômato finito que reconheça L.
b. Existe pelo menos uma gramática linear à esquerda que gera L, um autômato finito que reconhece L e uma expressão regular que gera L.
c. É possível garantir a existência de uma expressão regular que gera L, mas não de uma gramática linear à direita ou de um autômato finito que gere/reconheça L.
d. É possível garantir a existência de um autômato finito não determinístico que reconhece L, mas não de uma expressão regular que gera L.
e. É possível garantir a existência de um autômato finito determinístico que reconhece L, mas não de uma gramática linear à esquerda que gere L.
Observe a gramática a seguir.
G = ({S, A, B, T}, {a, b}, P, S)
P = {S → aAS | bBS | T
Aa → aA
Ab → bA
Ba → aB
Bb → bB
BT → Tb
AT → Ta
T → ε }Sobre essa gramática, assinale a alternativa correta.
a. É livre de contexto e aceita a linguagem {ww | w ∈ {a, b}*}.
b. É sensível ao contexto e aceita a linguagem {ww | w ∈ {a, b}*}.
c. É irrestrita e aceita a linguagem {ww | w ∈ {a, b}*}.
d. É sensível ao contexto e aceita a linguagem {wwR | w ∈ {a, b}*}.
e. É irrestrita e aceita a linguagem {wwR | w ∈ {a, b}*}.
A característica que torna as gramáticas livres de contexto especialmente adequadas à formalização sintática das linguagens de programação é a sua capacidade de representação de construções aninhadas, que são frequentemente encontradas em linguagens dessa categoria. Construções aninhadas costumam ocorrer em linguagens de programação, por exemplo, na construção de expressões aritméticas, em que subexpressões são delimitadas, através do uso de parênteses; na estruturação do fluxo de controle, em que comandos internos são inseridos como parte integrante de outros externos; na estruturação do programa, em que blocos, módulos, procedimentos e funções são empregados para criar diferentes escopos. Desenvolva uma gramática livre de contexto que gere a linguagem aibjajbi, com i > 0 e j > 0.
G = ({S, X}, {a, b}, P, S)
P = {S → aSb | aXb
X → bXa | ba }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:
Conforme exposto, converta a gramática livre de contexto apresentada a seguir na Forma Normal de Chomsky.
G = ({S, X, Y}, {a, b}, P, S)
P = {S → XY
X → aXb | ε
Y → bYa | ε }G = ({S, S₀, S₁, X, X₀, Y, Y₀, A₀, A₁, A₂, A₃, A₄, A₅, A₆, A₇, B₀, B₁, B₂, B₃, B₄, B₅, B₆, B₇}, {a, b}, P, S)
P = {S → XY | A₀S₀ | A₁B₁ | B₂S₁ | B₃A₃ | ε
S₀ → XB₀
S₁ → YA₂
X → A₄X₀ | A₅B₅
X₀ → XB₄
Y → B₆Y₀ | B₇A₇
Y₀ → YA₆
A₀ → a
A₁ → a
A₂ → a
A₃ → a
A₄ → a
A₅ → a
A₆ → a
A₇ → a
B₀ → b
B₁ → b
B₂ → b
B₃ → b
B₄ → b
B₅ → b
B₆ → b
B₇ → b }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 acc como prefixo, cac ou cba como subpalavra e acb como sufixo}.
G = ({A, B, C, D, E, F, G, H, I, J, K, L}, {a, b, c}, P, A)
P = {A → aB
B → cC
C → cD | cE | cG
D → aD | bD | cD | cE | cG
E → aF
F → cI | cK
G → bH
H → aI | aJ
I → aI | bI | cI | aJ
J → cK
K → bL
L → ε }(Ramos, 2009) As formas normais estabelecem restrições rígidas na definição das produções, sem reduzir o poder de geração das Gramáticas Livres de Contexto, sendo usadas principalmente no desenvolvimento de algoritmos (com destaque para reconhecedores de linguagens) e na prova de teoremas. Por exemplo, diz-se que uma Gramática Livre de Contexto G = (V, Σ, P, S) obedece à Forma Normal de Greibach se todas as suas produções p ∈ P forem da forma:
Conforme exposto, apresente a Forma Normal de Greibach da gramática livre de contexto a seguir.
G = ({S, X, Y}, {a, b, c}, P, S)
P = {S → Xc | c
X → Sb | Yb
Y → Yb | a }G = ({W, X, X₀, Y, Y₀, B₀, B₁, B₂, B₃, B₄, B₅, B₆, B₇, B₈, B₉, B₁₀, B₁₁, B₁₂, B₁₃, C₀, C₁, C₂, C₃, C₄, C₅}, {a, b, c}, P, W)
P = {W → cB₀X₀C₀ | aY₀B₁X₀C₁ | aB₂X₀C₂ | cB₃C₃ | aY₀B₄C₄ | aB₅C₅ | c
X → cB₆X₀ | aY₀B₇X₀ | aB₈X₀ | cB₉ | aY₀B₁₀ | aB₁₁
X₀ → cB₁₂X₀ | cB₁₃
Y → aY₀ | a
Y₀ → bY₀ | b
B₀ → b
B₁ → b
B₂ → b
B₃ → b
B₄ → b
B₅ → b
B₆ → b
B₇ → b
B₈ → b
B₉ → b
B₁₀ → b
B₁₁ → b
B₁₂ → b
B₁₃ → b
C₀ → c
C₁ → c
C₂ → c
C₃ → c
C₄ → c
C₅ → c }Ybadoo - Soluções em Software Livre • Copyright 2009/2024 • 