Turmas - 2º Semestre de 2019(ENADE, 2017) Considere o seguinte alfabeto: Σ = {(, ), 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -}.
Considere, ainda, uma linguagem L definida sobre esse alfabeto: L = {w | w ∈ Σ*, para cada ocorrência de ( em w, existe uma ocorrência de )}.
Por exemplo, a cadeia (2 + (3 - 4)) pertence a L, mas a cadeia (2 + (3 - 4) não pertence a L.
Com relação a linguagem L, avalie as asserções a seguir e a relação proposta entre elas.
I. A linguagem L não pode ser considerada regular.
PORQUE
II. Autômatos finitos não possuem mecanismos que permitam contar infinitamente o número de ocorrências de determinado símbolo em uma cadeia.
A respeito dessas asserções, assinale a opção correta.
a. as asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
b. as asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
c. a asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
d. a asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
e. as asserções I e II são proposições falsas.
Observe a gramática regular apresentada a seguir:
G = ({S, A}, {0, 1, 2}, P, S)
P = {S → 0A | 1S | 2S
A → 0A | 1S | 2S | ε }Sobre essa gramática, assinale a alternativa correta:
a. é regular à direita e aceita a linguagem {w | w é um número ternário par}.
b. é regular à esquerda e aceita a linguagem {w | w é um número ternário ímpar}.
c. é regular à direita e aceita a linguagem {w | w é um número ternário divisível por 3}.
d. é regular à esquerda e aceita a linguagem {w | w é um número ternário divisível por 4}.
e. é regular à direita e aceita a linguagem {w | w é um número ternário divisível por 5}.
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 [[a];a;[a]] sobre a gramática livre de contexto G2 é necessário a aplicação de quantas produções?
G2 = ({S, L}, {;, [, ], a}, P2, S)
P2 = {S → a | [L]
L → S;L | S}a. 10 produções.
b. 11 produções.
c. 12 produções.
d. 13 produções.
e. 14 produções.
(Hopcroft, 2002) Dizemos que um símbolo X é útil para uma gramática G = (V, T, P, S) se existe alguma derivação da forma S ⇒ αXβ ⇒ w, onde w está em T*. Observe que X pode estar em V ou T, e que a forma sentencial αXβ poderia ser a primeira ou a última na derivação. Se X não é útil, dizemos que ele é inútil. Evidentemente, a retirada de símbolos inúteis de uma gramática não irá alterar a linguagem gerada, e assim podemos detectar e eliminar todos os símbolos inúteis.
Considerando a gramática livre de contexto apresentada a seguir, analise as seguintes assertivas.
G = ({A, B, C, D, E, F, G}, {x, y, z}, P, A)
P = {A → xFy | BxE
B → xG | Gy
C → y | yG
D → zC | zzB
E → y | Fx
F → Gy | Exx
G → BzB }A análise permite concluir que:
a. apenas as assertivas I e II estão corretas.
b. apenas as assertivas I e III estão corretas.
c. apenas as assertivas II e III estão corretas.
d. apenas as assertivas II e IV estão corretas.
e. apenas as assertivas III e IV estão corretas.
(Ramos, 2009) 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 seguinte linguagem L = {w ∈ {a, b}* | w = ambn com (m = n) ou (m ≠ n)}.
G = ({S, X, Y}, {a, b}, P, S)
P = {S → XY
X → aX | ε
Y → bY | ε }(Menezes, 2000) 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, prove que a gramática apresentada a seguir é ambígua.
G = ({A, B, C}, {if, else, i, j, k, x, y, z, (, )}, P, A)
P = {A → if (B) A | if (B) A else A | C
B → i | j | k
C → x | y | z }
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.
G = ({A, B, C, D, E, F}, {x, y, z}, P, A)
P = {A → Exy | zD
B → DF | xCy
C → xEB | FCz
D → yCA | AFA | ε
E → AzC | BEyz
F → zAy | D | ACB }G = ({A, D, D0, F, F0, F1, Y0, Z0, Z1}, {y, z}, P, A)
P = {A → Z0D | z
D → AD0 | AA
F → Z1F0 | AF1 | AA
D0 → FA
F0 → AY0
F1 → FA
Y0 → y
Z0 → z
Z1 → z(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:
A → σα, σ ∈ Σ, α ∈ N*
Conforme exposto, apresente a Forma Normal de Greibach da gramática livre de contexto a seguir.
G = ({S, A, B, C}, {b, c, d}, P, S)
P = {S → BA
A → AAC | b
B → AAB | Cc
C → SC | d }G = ({A, B, B0, C, C0, C1, C2, C3, C4, C5, C6, C7, C8, C9, C10, C11, D, D0}, {b, c, d}, P, A)
P = {A → bB0BCB | bBCB | bB0BCBDD0C0B | bBCBDD0C1B | dD0C2B | bB0BCBDC3B | bBCBDC4B | dC5B
B → bB0 | b
B0 → bB0DB0 | bDB0 | bB0D | bD
C → bB0BC | bBC| bB0BCBDD0C6 | bBCBDD0C7 | dD0C8 | bB0BCBDC9 | bBCBDC10 | dC11
C0 → c
C1 → c
C2 → c
C3 → c
C4 → c
C5 → c
C6 → c
C7 → c
C8 → c
C9 → c
C10 → c
C11 → c
D → bB0BCBDD0 | bBCBDD0 | dD0 | bB0BCBD | bBCBD | d
D0 → cBDD0 | cBDYbadoo - Soluções em Software Livre • Copyright 2009/2024 • 