DISCIPLINA: ASPECTOS TEÓRICOS DA COMPUTAÇÃO

Linguagens recursivamente enumeráveis e sensíveis ao contexto

Alunos: David Sanford, David Silva e Luan Martins

Fortaleza – CE

SUMÁRIO

1. DEFINIÇÃO DO PROBLEMA

1.1 Apresentação do Tema do Trabalho

1.2 Situação Problemática

2. OBJETIVOS

2.1 Geral

2.2 Específico

3. JUSTIFICATIVA

4. METODOLOGIA

5. CONSIDERAÇÕES FINAIS

6. REFERÊNCIAS BIBLIOGRÁFICAS

1. Definição do Problema

1.1 Apresentação do Tema do Trabalho

Este trabalho trata de um estudo das linguagens sensíveis ao contexto e recursivamente enumeráveis. Nesse estudo será explicado os conceitos, propriedades e aplicações que caracterizam essas linguagens. Além disso, será a presentado uma problematização a ser discutida em sala.

A fim de generalizar um a maneira de fazer computação, Alan Turing propôs um modelo de computação teórica que simulava o máximo possível as atitudes humanas relacionadas a computação. A máquina de Turing, como ficou conhecido, é responsável pelo desenvolvimento dos atuais computadores e do conceito de algoritmo.

É impossível demonstrar formalmente se a máquina de Turing é, de fato, o mais genérico dispositivo de computação, no entanto Alonzo Church formulou uma hipótese onde afirmava que qualquer função computável pode ser processada por uma máquina de Turing.

A máquina de Turing, em essência, é um autômato cuja fita não possui tamanho máximo e pode ser usada simultaneamente como dispositivo de entrada, saída e memória de trabalho.

As linguagens apresentadas possuem classificações do tipo 1 e tipo 0 respectivamente. As linguagens sensíveis ao contexto (tipo 1) são aquelas que podem ser aceitas por uma máquina de Turing com fita limitada, ou seja, uma máquina de Turing com limitação finita no tamanho da fita. As linguagens recursivamente enumeráveis (tipo 0) por uma máquina de Turing, elas representam o conjunto de todas as linguagens que podem ser reconhecidas mecanicamente e em tempo finito.

A sensibilidade ao contexto tem como propriedade sentenças que exibem características de dependência entre trechos distintos, isso significa que 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.

A necessidade de criar a recursivamente enumerável deu-se ao fato de que não se conhece uma maneira de decidir se uma função irá parar para uma dada instância, logo uma característica dela é existir pelo menos uma cadeia C em uma linguagem L, aceita por uma máquina de Turing, onde inicia-se uma sequência interminável de movimentações em seu procedimento.

1.2 Situação Problemática

Em termos computacionais, existem mais problemas não computáveis do que problemas computáveis. A classe das linguagens recursivamente enumeráveis inclui algumas para as quais é impossível determinar mecanicamente se uma palavra não pertence a uma linguagem, embora seja possível determinar se pertence.

Um problema computável pode ser parcialmente solucionável, ou seja, para uma determinada linguagem pertencente a classe das recursivamente enumeráveis, existe pelo menos uma palavra não pertencente a ela que faz a máquina que a reconhece processar indefinidamente.

Esse problema predominantemente matemático é chamado de indecidível. Alguns dos problemas estão na lógica, envolvem máquinas abstratas, matrizes, teoria combinatória de grupos, topologia etc.

A solução desses problemas ajudaria pesquisadores das áreas de criptografia, nos problemas de lógica, análise de algoritmos e computação como um todo, para os de máquinas abstratas.

Um dos 23 problemas propostos por David Hilbert, o décimo problema, está na lista de problemas indecidíveis. Ele pede para descrever, em um número finito de operações, se uma dada equação diofantina tem raiz (es) inteira (s), uma equação diofantina é uma equação polinomial que permite a duas ou mais variáveis assumirem apenas valores inteiros.

2. Objetivos

2.1 Geral

Proporcionar o aprendizado sobre os temas linguagens sensíveis ao contexto e as recursivamente enumeráveis.

2.2 Específicos

Promover a participação dos alunos (as). Além disso, desenvolver uma discussão envolvendo a problematização e uma atividade prática sobre o tema apresentado.

3. Justificativa

O estudo permitirá que os conteúdos que serão abordados posteriormente, como a construção de compiladores, sejam melhor compreendidos. Ademais, colabora para o surgimento de ideias que eventualmente possam contribuir para a solução dos problemas em aberto, no caso das linguagens recursivamente enumeráveis.

4. Metodologia

Será utilizado o método de seminário integrado. O conteúdo será explicado com auxílio de slides de apresentações juntamente com técnicas de ensino didáticas dentro da realidade do contexto.

O seminário integrado permite trabalhar diferentes conteúdos de maneira interativa dentro da sala de aula proporcionando um melhor aprendizado entre os alunos. Os slides ajudam a aperfeiçoar o entendimento do que está sendo explicado por meio de imagens, além de servir como direcionamento de raciocínio por parte de quem está explicando.

Em um primeiro momento serão explicados os conceitos e em seguida a sua aplicação dentro do contexto em que está sendo estudado. No segundo momento será abordado a problematização seguido de uma discussão.

5. Considerações Finais

Espera-se que com este trabalho a maioria dos alunos consigam entender e saber usar os conteúdos dos temas abordados. Espera-se o desenvolvimento de um pensamento crítico para que novas formas de conhecimento surjam e que não fiquem limitados pelos conhecimentos já existentes, pois atualmente carecemos de novas descobertas.

6 Referências Bibliográficas

SALES, J. de O. C. B. e BRAGA, M. M. S. de C. Didática Geral – unidade 3: a organização do trabalho pedagógico. Apostila da Formação Pedagógica na modalidade EAD do CED/UECE.

RAMOS M. V. MARCUS. Linguagens formais e autômatos.

MENEZES, B. P. Linguagens formais e autômatos. Instituto de informática da UFRGS.