Exercícios Linguagens Sensíveis ao Contexto e Recursivamente Enumeráveis

Prévia do material em texto

MINISTÉRIO DE EDUCAÇÃO
 UNIVERSIDADE FEDERAL RURAL DO RIO DE JANEIRO 
Instituto Multidisciplinar 
Departamento de Ciência da Computação
Curso de Ciência da Computação 
Linguagens Formais e Autômatos
Lista de Exercícios No. 04
Linguagens Sensíveis ao Contexto e Recursivamente Enumeráveis
1) Qual a diferença fundamental entre a classe das Linguagens Recursivas e a classe das Linguagens
Recursivamente Enumeráveis?
2) Por que nem toda Gramática Sensível ao Contexto é uma Gramática Livre de Contexto? 
3) Para quais classes de linguagens da hierarquia de Chomsky pode-se afirmar que, para qualquer linguagem
da classe, sempre existe um algoritmo que aceita a linguagem e que sempre para qualquer entrada?
Justifique a sua resposta para cada classe.
4) Determine como verdadeiro (V) ou falso (F) as afirmações a seguir:
( ) Uma Linguagem Sensível ao Contexto é reconhecida por uma Máquina de Turing com fita limitada à
esquerda e à direita.
( ) Toda Linguagem Recursivamente Enumerável é uma Linguagem Sensível ao Contexto.
( ) Toda Linguagem Recursiva é uma Linguagem Recursivamente Enumerável.
( ) Um problema semi-decidível sempre para quando recebe um parâmetro que não pertence a linguagem.
( ) Qualquer linguagem pode ser reconhecida por uma Máquina de Turing com fita ilimitada à direita.
( ) Se uma linguagem é Turing Decidível, então não se pode afirmar que as palavras não pertencentes a esta
linguagem formam também uma linguagem Turing Decidível.
( ) Um problema é decidível se existe uma Linguagem Recursiva que o satisfaz.
( ) A Linguagem Recursivamente Enumerável engloba todas as linguagens conhecidas, com exceção das
Linguagens Turing Reconhecível.
( ) Se um problema é não semi-decidível então não existe uma Máquina de Turing capaz de resolvê-lo.
( ) Se L é Turing Reconhecível e L'(palavras não pertencentes a L) é Turing Reconhecível, então L é Turing
Decidível.
( ) Nem toda Linguagem Regular e Livre de Contexto é uma Linguagem Sensível ao Contexto.
5) Explique, intuitivamente, com suas palavras o porque das afirmações estarem corretas:
a) “Se L é Turing Decidível, então L'(conjunto das palavras não reconhecidas por L) é Turing Decidível.”
b) “Se L é Turing Reconhecível e L' é Turing Reconhecível, então L é Turing Decidível.”
6) (POSCOMP 2014) Observe a gramática a seguir.
S → aAbba
aAb → aabbbA | ab
bAb → bbA
bAa → Bbaa
bB → Bb
aB → aA
Sobre essa gramática, assinale a alternativa correta.
(a) É irrestrita e aceita a linguagem {anb2n + 1an | n ≥ 1}.
(b) É irrestrita e aceita a linguagem {anb2nan | n ≥ 1}.
(c) É sensível ao contexto e aceita a linguagem {anb2n + 1an | n ≥ 1}.
(d) É sensível ao contexto e aceita a linguagem {anb2nan | n ≥ 1}.
(e) É livre de contexto e aceita a linguagem {anb2n+ 1an | n ≥ 1}.
7) (Exercício complementar) Desenvolva um programa em computador que simule qualquer Máquina de
Turing. As entradas devem ser os componentes da máquina e a palavra a ser processada. Como saídas, o
simulador deve apresentar o estado final da máquina simulada, o conteúdo da fita e o número de
movimentos da cabeça da fita.