Turmas - 2º Semestre de 2016Quando 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 abcdac sobre a gramática livre de contexto G2 é necessário a aplicação de quantas produções?
G2 = ({S, A, B, C}, {a, b, c, d}, P2, S)
P2 = {S → ABC
A → aA | ε
B → bB | CdA
C → cC | ε}a. 10 produções
b. 11 produções
c. 12 produções
d. 13 produções
e. 14 produções
A característica que torna as gramáticas livres do 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.
Uma expressão numérica é composta por parênteses ( ), colchetes [ ], chaves { }, números e os símbolos de operação. Entre os parênteses, colchetes e chaves, primeiro resolvemos a parte interna dos parênteses, em seguida os colchetes e, logo após, as chaves. Entre os símbolos de operação, primeiro resolvemos a multiplicação * e/ou divisão /, e logo após, a adição + e/ou subtração -.
Conforme exposto, desenvolva uma gramática livre de contexto, não ambígua, que reconheça expressões numéricas, como por exemplo 25 + {14 - [25 * 4 + 40 - (20 / 2 + 10)]}.
G = ({A, B, C, D, E, F, G, H, I, J, K, N, X}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, *, /, {, }, [, ], (, )}, P, A)
P = {A → A + B | A - B | B
B → B * C | B / C | C
C → { D } | N
D → D + E | D - E | E
E → E * F | E / F | F
F → [ G ] | N
G → G + H | G - H | H
H → H * I | H / I | I
I → ( J ) | N
J → J + K | J - K | J
K → K * N | K / N | N
N → NX | X
X → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9}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:
1. A → BC, ou
2. A → a
Conforme exposto, qual das gramáticas livres de contexto corresponde à Forma Normal de Chomsky da gramática livre de contexto G3.
G3 = ({W, X, Y, Z}, {a, b}, P3, W)
P3 = {W → aWb | Y
X → bXa | Y
Y → aZb
Z → ε}a.
G = ({W, X, Y, A1, A2, A3, B1, B2, B3}, {a, b}, P, W)
P = {W → A1X | A2B1
X → WB2
Y → A3B3
A1 → a
A2 → a
A3 → a
B1 → b
B2 → b
B3 → b}b.
G = ({W, X, Y, A1, A2, A3, B1, B2, B3}, {a, b}, P, W)
P = {W → B1X | A2B1
X → WA2
Y → A3B3
A1 → a
A2 → a
A3 → a
B1 → b
B2 → b
B3 → b}c.
G = ({W, X, A1, A2, B1, B2}, {a, b}, P, W)
P = {W → B1X | A2B1
X → WA2
A1 → a
A2 → a
B1 → b
B2 → b}d.
G = ({W, X, A1, A2, B1, B2}, {a, b}, P, W)
P = {W → A1X | A2B1
X → WB2
A1 → a
A2 → a
B1 → b
B2 → b}e.
G = ({W, X, Y, Z, S, A1, A2, A3, A4, A5, B1, B2, B3, B4, B5}, {a, b}, P, W)
P = {W → A1Z | A2B1
X → B3S | A3B4
Y → A5B5
Z → WB2
S → XA4
A1 → a
A2 → a
A3 → a
A4 → a
A5 → a
B1 → b
B2 → b
B3 → b
B4 → b
B5 → b}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:
1. A → σα, σ ∈ Σ, α ∈ N*
Conforme exposto, apresente a Forma Normal de Greibach da gramática livre de contexto G4.
G4 = ({S, W, A}, {x, y, z}, P4, S)
P4 = {S → Wx
W → Sy | Ay
A → Sz | z}G = ({A, B, C, D, E, X1, X2, X3, X4, X5, X6, X7, X8, Y1, Y2, Y3, Y4, Y5, Y6, Y7, Y8, Y9, Y10, Z1, Z2, Z3, Z4}, {x, y, z}, P, A)
P = {A → zC1Y1B1X1 | zY2B1X2 | zC1Y3X3 | zY4X4
B → zC1Y5B1 | zY6B1 | zC1Y7 | zY8
B1 → xY9B1 | xY10
C → zC1 | z
C1 → yB1X5Z1C1 | yX6Z2C1 | yB1X7Z3 | yX8Z4
X1 → x
X2 → x
X3 → x
X4 → x
X5 → x
X6 → x
X7 → x
X8 → x
Y1 → y
Y2 → y
Y3 → y
Y4 → y
Y5 → y
Y6 → y
Y7 → y
Y8 → y
Y9 → y
Y10 → y
Z1 → z
Z2 → z
Z3 → z
Z4 → z}Linguagens sensíveis ao contexto são aquelas cujas sentenças exibem características de dependência – ou vinculação – entre trechos distintos das mesmas. Ou seja, determinadas partes de uma sentença só serão consideradas válidas se ocorrerem simultaneamente a trechos relacionados, presentes em outras regiões da mesma sentença. Daí a origem do nome "sensibilidade ao contexto".
Formalmente, uma gramática sensível ao contexto G = (V, Σ, P, S) é aquela cujas regras do conjunto P obedecem ao formato α → β, onde:
Analise as seguintes afirmativas sobre gramáticas sensíveis ao contexto:
I. A gramática sensível ao contexto G5 representa a linguagem {anbncn | n ≥ 1}.
G5 = ({S, Q}, {a, b, c}, P5, S)
P5 = { S → aSQ | abc
bQc → bbcc
cQ → Qc}II. A gramática sensível ao contexto G6 representa a linguagem {anbncn | n ≥ 1}.
G6 = ({S, B, C}, {a, b, c}, P6, S)
P6 = { S → aSBC | aBC
CB → BC
aB → ab
bB → bb
bC → bc
cC → cc}III. A gramática sensível ao contexto G7 representa a linguagem {anbnan | n ≥ 1}.
G7 = ({S, B, X}, {a, b}, P7, S)
P7 = { S → aBSa | aBXa
Ba → aB
BX → Xb
aX → a}A análise permite concluir que:
a. apenas a afirmativa I está correta.
b. apenas a afirmativa II está correta.
c. apenas a afirmativa III está correta.
d. apenas as afirmativas I e II estão corretas.
e. apenas as afirmativas II e III estão corretas.
Uma gramática linear à esquerda é aquela em que todas as produções exibem as seguintes características:
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.
Conforme exposto, a gramática linear à esquerda G8 representa qual expressão regular.
G8 = ({A, B, C, D, E, F, G, H, I}, {a, b, c}, P8, A)
P8 = {A → Bc
B → Cb | Db
C → Ca | Cb | Cc | Db
D → Ea | Ga
E → Fc | Hc
F → Fa | Fb | Fc | Ga
G → Hc
H → Ib
I → ε}a. (bca(a + b + c)*cab(a + b + c)*bc)
b. (bca(ε + (a + b + c)*c)a(ε + b(a + b + c)*)bc)
c. (bca(ε + (a + b + c)*ca)(ε + b(a + b + c)*)bc)
d. (bca(ε + (a + b + c)*)cab(ε + (a + b + c)*)bc)
e. (bc(ε + a(a + b + c)*c)a(ε + b(a + b + c)*)bc)
Ybadoo - Soluções em Software Livre • Copyright 2009/2024 • 