Problemas de decisão em teoria de linguagens regulares

Abstract

Um problema de decisão consiste num conjunto de perguntas cujas respostas são "sim" ou "não" . A solução para um problema de decisão é um procedimento completo, mecânico e determinista, sendo assim (muitas vezes) chamado de procedimento efetivo. Um problema de decisão é indecidível se não houver nenhum procedimento/algoritmo que resolva o problema, caso contrário, é decidível. A capacidade das máquinas de Turing de retornar respostas afirmativas e negativas, torna-as um sistema matemático adequado para a construção de soluções para problemas de decisão. As máquinas de Turing que se limitam a ler uma determinada palavra podem ser vistas como autómatos finitos. O autómato finito é um modelo matemático da computação de um sistema com entradas e saídas discretas. As linguagens regulares são as linguagens representáveis por uma expressão regular, constituindo o nível mais elementar da hierarquia do linguista Noam Chomsky. Kleene demonstrou que as linguagens regulares são precisamente as linguagens reconhecidas pelos autómatos finitos, fundando assim a teoria das linguagens regulares e dos autómatos finitos. Neste trabalho estudam-se alguns problemas de decisão envolvendo linguagens regulares, quando estas são representadas por autómatos finitos ou expressões regulares. Especificamente, apresentamos e analisamos algoritmos para o problema de decidir se uma dada linguagem é vazia, bem como o problema de decidir se uma dada linguagem é infinita.

A decision problem is a set of questions that are answered "yes" or "no". The solution to a decision problem is a complete, mechanical and deterministic procedure, so it is (often) called an effective procedure. A decision problem is undecidable if there is no procedure/algorithm that solves the problem, otherwise it is decidable. The ability of Turing machines to return affirmative and negative answers makes them a suitable mathematical system for building solutions to decision problems. Turing machines that merely read a certain word can be seen as finite automata. The finite automaton is a mathematical model of the computation of a system with discrete inputs and outputs. Regular languages are the languages representable by a regular expression, constituting the most elementary level of the linguist Noam Chomsky’s hierarchy. Kleene demonstrated that the regular languages are precisely the languages recognized by finite automata, thus founding the theory of regular languages and finite automata. In this work we study some decision problems for regular languages, when languages are given both by finite automata and regular expressions. Specifically we present and analyze algorithms for the problem of deciding if the given language is empty, as well as for the problem of deciding if the given language is infinite.