Turmas - 2º Semestre de 2017(POSCOMP, 2016) Também conhecidas como dispositivos generativos, dispositivos de síntese, ou ainda dispositivos de geração de cadeias, as gramáticas constituem sistemas formais baseados em regras de substituição, através dos quais é possível sintetizar, de forma exaustiva, o conjunto das cadeias que compõem uma determinada linguagem. Dessa forma, a linguagem L = {anbm | n ≤ m}, para n ≥ 0 e m ≥ 0, é gerada pela gramática:
a. Regular S → aA, A → aA | bA | ε.
b. Sensível ao contexto S → aSBC, S → aBC, CB → BC, aB → ab, bB → bb, bC → bc, cC → cc.
c. Livre de contexto S → aA, A → aAb | B, B → Bb | ε.
d. Regular S → aA, A → aA | bB, B → bB | ε.
e. Livre de contexto S → aSb | A, A → Ab | ε.
(Ramos, 2009) A derivação de uma forma sentencial em uma gramática livre de contexto é uma derivação mais à esquerda, quando a substituição de um não-terminal pelo lado direito de uma produção que o define é feita substituindo-se sempre o não-terminal que ocorre mais à esquerda na cadeia que representa a forma sentencial em questão. De maneira análoga, uma derivação mais à direita, é aquela em que é sempre o não-terminal mais à direita, na forma sentencial, que é substituído pela sua definição. Por exemplo, considerando a gramática E → T + E | T, T → a * T | a e a sentença a + a, se obtêm as seguintes sequências de derivações:
Derivação à extrema esquerda
E • T + E • a + E • a + T • a + a
Derivação à extrema direita
E • T + E • T + T • T + a • + a
Observa-se, que em ambos os casos, o número de produções utilizadas na sequência de derivações é o mesmo, cinco produções.
Considerando a gramática livre de contexto G2 e a sentença a * (a + a) * a, quantas produções são necessárias para se concluir a derivação?
G2 = ({A, B, C, D, E}, {a, +, *, (, )}, P2, A)
P2 = {A → CB
B → +CB | ε
C → ED
D → *ED | ε
E → (A) | a}a. 17 produções.
b. 18 produções.
c. 19 produções.
d. 20 produções.
e. 21 produções.
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, converta a gramática livre de contexto G2, apresentada no exercício anterior, na Forma Normal de Chomsky.
G3 = ({A, A1, B, B1, C, C1, D, D1, E, E1, X1, X2, Y1, Y2, R1, R2, R3, S1, S2, S3}, {a, +, *, (, )}, P3, A)
P3 = {A → CB | ED | R1A1 | a
A1 → AS1
B → X1B1 | X2C
B1 → CB
C → ED | R2C1 | a
C1 → AS2
D → Y1D1 | Y2E
D1 → ED
E → R3E1 | a
E1 → AS3
X1 → +
X2 → +
Y1 → *
Y2 → *
R1 → (
R2 → (
R3 → (
S1 → )
S2 → )
S3 → )}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, converta a gramática livre de contexto G4 para a Forma Normal de Greibach.
G4 = ({S, A}, {(, )}, P4, S)
P4 = {S → () | SS | (A
A → S)}G4 = ({A, A1, B, X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11}, {(, )}, P4, A)
P4 = {A → (X1A1 | (BA1 | (X2 | (B
A1 → (X3A1A1 | (BA1A1 | (X4A1 | (BA1 | (X5 | (B
B → (X6A1X7 | (BA1X8 | (X9X10 | (BX11
X1 → )
X2 → )
X3 → )
X4 → )
X5 → )
X6 → )
X7 → )
X8 → )
X9 → )
X10 → )
X11 → )}As gramáticas pertencentes à última classe definida pela Hierarquia de Chomsky recebem a denominação de irrestritas, ou do tipo 0. Como o próprio nome sugere, trata-se de gramáticas sobre as quais não é imposta nenhuma restrição quanto ao formato de suas produções, exceto pelo fato de que o lado esquerdo das mesmas deva sempre conter pelo menos um símbolo não-terminal. Considere a gramática irrestrita G5 apresentada a seguir:
G5 = ({S, A, B, C}, {a, b}, P5, S)
P5 = {S → aAS | bBS | C
Aa → aA
Ab → bA
Ba → aB
Bb → bB
AC → Ca
BC → Cb
C → ε}Qual das seguintes sentenças é reconhecida pela gramática irrestrita G5?
a. aaabbb.
b. aabaaaba.
c. aabbaa.
d. aabbbb.
e. aababaa.
As linguagens e as gramáticas livres de contexto foram inicialmente concebidas com a intenção de permitir a formalização sintática das linguagens naturais. Logo se percebeu, no entanto, que as linguagens naturais são significativamente mais complexas do que a classe de linguagens representáveis através das gramáticas livres de contexto, diminuindo em muito, em consequência, o interesse dos estudiosos das linguagens naturais pelas gramáticas desse tipo. Por outro lado, as linguagens livres de contexto despertaram um interesse muito grande na comunidade científica ligada à área de computação, que via grandes possibilidades de aplicação dessa classe de linguagens na análise e na formalização de linguagens artificiais, em particular, as linguagens de programação. Desenvolva uma gramática livre de contexto que reconheça o comando switch/case na linguagem de programação C, conforme apresentado a seguir:
switch (variável) {
case constante: instruções; break;
case constante: instruções; break;
default: instruções;
}Observações:
1. variável, constante e instruções são não-terminais previamente definidos, ou seja, não é necessário a sua especificação na solução do exercício.
2. a quantidade de blocos case deve ser maior do que zero.
3. o bloco default é opcional, bem como terminar os blocos case com o comando break.
G6 = ({switch, switch-body, break, switch-end}, {switch, case, default, :, (, ),;, {, }}, P6, switch)
P6 = {<switch> ::= switch (<variável>) {<switch-body>
<switch-body> ::= <switch-body> case <constante>: <instruções>;<break> | case <constante>: <instruções>;<break><switch-end>
<break> ::= break; | ε
<switch-end> ::= default : <instruções>;} | }}Analise as assertivas referentes ao método de exclusão de símbolos inúteis, empregado na simplificação de gramáticas livre de contexto. Dado uma gramática livre de contexto G = (V, Σ, P, S), então:
A análise permite concluir que:
a. apenas a assertiva I está correta.
b. apenas a assertiva II está correta.
c. apenas a assertiva III está correta.
d. apenas as assertivas I e II estão corretas.
e. apenas as assertivas II e III estão corretas.
Gramáticas lineares, à esquerda ou à direita, também conhecidas como gramáticas do tipo 3, geram linguagens denominadas regulares, ou simplesmente do tipo 3, e 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. Observe a gramática linear G8 apresentada a seguir:
G8 = ({S, A}, {a, b}, P8, S)
P8 = {S → aS | aA
A → bA | ε}Sobre essa gramática, assinale a alternativa correta:
a. é linear à direita e aceita a linguagem regular {anbm | n ≥ 0 e m ≥ 0}.
b. é linear à esquerda e aceita a linguagem regular {anbm | n > 0 e m ≥ 0}.
c. é linear à direita e aceita a linguagem regular {anbm | n ≥ 0 e m > 0}.
d. é linear à esquerda e aceita a linguagem regular {anbm | n ≥ 0 e m ≥ 0}.
e. é linear à direita e aceita a linguagem regular {anbm | n > 0 e m ≥ 0}.
Ybadoo - Soluções em Software Livre • Copyright 2009/2025 • 