Turmas - 1º Semestre de 2018
Turmas
1º Semestre de 2018

(Ramos, 2009) O estudo sistemático das linguagens formais teve um forte impulso no final da década de 1950, quando o linguista Noam Chomsky publicou dois artigos apresentando o resultado de suas pesquisas relativas à classificação hierárquica das linguagens, conhecida como Hierarquia de Chomsky, que tem como principal mérito agrupar as linguagens em classes, de tal forma que elas possam ser hierarquizadas de acordo com a sua complexidade relativa. O interesse prático pela Hierarquia de Chomsky se deve especialmente ao fato de ela viabilizar a escolha da forma mais econômica para a realização dos reconhecedores das linguagens, de acordo com a classe a que elas pertençam nessa hierarquia, evitando-se, portanto, o uso de formalismos mais complexos que o necessário, e o emprego de reconhecedores desnecessariamente ineficientes para as linguagens de menor complexidade. Analise as seguintes assertivas sobre a Hierarquia de Chomsky.

1. As linguagens regulares constituem a classe de linguagens mais simples dentro da Hierarquia de Chomsky, sendo reconhecidas por Autômatos Finitos.
2. As linguagens estritamente sensíveis ao contexto distinguem-se das linguagens livres de contexto por exibirem características de aninhamento, como é o caso da estruturação em blocos e comandos, ou ainda do uso de parênteses em expressões aritméticas nas linguagens de programação tradicionais.
3. As linguagens estritamente sensíveis ao contexto distinguem-se das linguagens livres de contexto por conterem sentenças as quais, por sua vez, exibem construções, ou conjuntos de símbolos, cuja validade é vinculada à presença de construções associadas em regiões distintas da mesma cadeia, como por exemplo, aquelas que existem entre a declaração e o uso de variáveis.
4. As linguagens estritamente irrestritas, ou seja, as irrestritas que não podem ser geradas por gramáticas sensíveis ao contexto, distinguem-se das linguagens sensíveis ao contexto por poderem ser reconhecidas por uma Máquina de Turing com fita limitada.

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.

Observe a gramática a seguir.

G = ({S, A}, {a, b, c}, P, S)
P = {S → Sc | Ab
     A → Aa | a}

Sobre essa gramática, assinale a alternativa correta:

a. é regular à direita e aceita a linguagem {aⁿbc^m | n ≥ 0 e m ≥ 0}.

b. é regular à esquerda e aceita a linguagem {aⁿbc^m | n ≥ 0 e m ≥ 0}.

c. é livre de contexto e aceita a linguagem {aⁿbc^m | n ≥ 0 e m ≥ 0}.

d. é regular à direita e aceita a linguagem {aⁿbc^m | n > 0 e m ≥ 0}.

e. é regular à esquerda e aceita a linguagem {aⁿbc^m | n > 0 e m ≥ 0}.

(Hopcroft, 2002) Embora ε-produções sejam uma conveniência em muitos problemas de projetos de gramáticas, não são essenciais. É claro que, sem uma produção que tenha um corpo ε, é impossível gerar o string vazio como um elemento da linguagem. Desse modo, o que realmente provamos é que, se a linguagem L tem uma CFG (Context-Free Grammar ou Gramática Livre de Contexto), então L - {ε} tem uma CFG sem ε-produções. Se ε não está em L, então a própria L é L - {ε}, e assim L tem uma CFG sem ε-produções.

Considerando a gramática livre de contexto apresentada a seguir, analise as seguintes assertivas.

G = ({S, A, B}, {a}, P, S)
P = {S → AAA | B
     A → aA | B
     B → ε}

1. Após a eliminação das ε-produções, as produções da variável A serão

   A → aA | a | A | B

2. Após a eliminação das ε-produções, as produções da variável S serão

   S → AAA | AA | A | B | ε

3. As produções da variável A não serão afetadas pela eliminação das ε-produções.
4. Após a eliminação das ε-produções, a variável B não terá mais produções na gramática resultante.

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.

(Hopcroft, 2002) Uma produção unitária é uma produção da forma A → B, onde tanto A quanto B são variáveis. Essas produções podem ser úteis em alguns casos, porém podem complicar certas provas, e também introduzem etapas extras em derivações que tecnicamente não precisam estar lá.

Considerando a gramática livre de contexto apresentada a seguir, analise as seguintes assertivas.

G = ({S, A, B, C}, {0, 1}, P, S)
P = {S → 0A0 | 1B1 | BB | B
     A → C
     B → S | A
     C → 0 | 1}

1. Após a eliminação das produções unitárias, as produções da variável B serão

   B → 0A0 | 1B1 | BB

2. Após a eliminação das produções unitárias, as produções da variável B serão

   B → 0A0 | 1B1 | BB | 0 | 1

3. Após a eliminação das produções unitárias, as produções da variável S serão

   S → 0A0 | 1B1 | BB | 0 | 1

4. Após a eliminação das produções unitárias, as produções da variável A serão

   A → 0A0 | 1B1 | BB

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.

(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 = ({S, A, B, C, D}, {a, b, c, d}, P, S)
P = {S → AB | C
     A → aAb | ab
     B → cBd | cd
     C → aCd | aDd
     D → bDc | bc }

(Rosa, 2010) 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 reconheça o operador ternário (?) em C, cuja sintaxe é condição ? verdadeiro : falso, onde condição é a condição que será testada, verdadeiro é o que fazer quando a condição for verdadeira, e falso é o que fazer quando a condição for falsa. Por exemplo, os seguintes comandos devem ser reconhecidos pela gramática livre de contexto.

condição ? operação : operação
condição ? condição ? operação : operação : operação
condição ? operação : condição ? operação : operação

Observação: condição e operação são não terminais previamente definidos, ou seja, não é necessário à sua especificação na solução do exercício.

G = ({S, condição, operação}, {?, :}, P, S)
P = {S → condição ? S : S
       | condição ? S : operação
       | condição ? operação : S
       | condição ? operação : operação }

(Ramos, 2009) Por uma questão de conveniência no estudo das gramáticas livres de contexto, muitas vezes é necessário submetê-las a simplificações que visam torná-las mais apropriadas para a demonstração de teoremas, para a verificação de propriedades, ou simplesmente para facilitar a sua análise. Tais simplificações consistem em manipulações gramaticas que não afetam a linguagem definida pela gramática original. Simplifique a gramática livre de contexto apresentada a seguir.

G = ({S, A, B, C, D}, {a, b, c, d}, P, S)
P = {S → aAa | bBb | ε
     A → C | a
     B → C | b
     C → CDE | ε
     D → A | B | ab }

G = ({S, A, B}, {a, b}, P, S)
P = {S → aAa | bBb | aa | bb | ε
     A → a
     B → b }

(Ramos, 2009) Uma gramática é 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. 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, converta a gramática livre de contexto a seguir para a Forma Normal de Greibach.

G = ({S, A, B, C}, {a, b, c, d}, P, S)
P = {S → AB | a
     A → SB | b
     B → SC | c
     C → d }

G = ({A, B, B₀, C, D}, {a, b, c, d}, P, S)
P = {A  → aCB₀C | bB₀C | aCC | bC | a
     B  → aCB₀ | bB₀ | aC | b
     B₀ → aCB₀CDCB₀ | bB₀CDCB₀ | aCCDCB₀ | bCDCB₀ | aDCB₀ | cCB₀ | aCB₀CDC | bB₀CDC | aCCDC | bCDC | aDC | cC
     C  → aCB₀CD | bB₀CD | aCCD | bCD | aD | c
     D  → d }