Artigo de Teoria dos Autômatos

TEORIA DOS AUTÔMATOS
Naun Lemos Belo [e-mail] Linguagens Formais – Regis

Resumo
Este artigo apresenta os conceitos introdutórios para o estudo dos autômatos. Neste, é abordado os principais tópicos da teoria dos conjuntos; além de conceituar símbolos, alfabetos, cadeias e gramáticas. Antes de entrar no assunto de autômatos (autômatos, autômatos finitos – determinísticos e não determinísticos) é importante conceituar as quatro gramáticas da Hierarquia de Chomsky.
Palavras-chave: Linguagens Formais. Autômatos. Linguagens Regulares.
Abstract
This article presents the introductory to the study of automata concepts. This is discussed the main topics of set theory; addition to conceptualize symbols, alphabets, strings and grammars.
Before entering the subject of automata (automata, finite automata - deterministic and nondeterministic) is important to conceptualize the four grammars Chomsky Hierarchy.
Key-words: Formal Languages. Automata. Regular Languages.

Introdução
O estudo da teoria dos autômatos consiste em ser o estudo de objetos matemáticos chamados de máquinas abstratas, e como problemas computacionais podem ser resolvidos fazendo uso destas máquinas.
Os autômatos funcionam tendo como base uma sequência de caracteres – chamada de cadeia – que são tidas como a entrada de uma máquina.
Para entender corretamente o funcionamento de um autômato, alguns conhecimentos prévios se fazem necessários; como é o caso do estudo sobre símbolos, alfabetos, cadeias ou palavras, linguagens e gramáticas. Porém, para o perfeito entendimento destes últimos é necessário ter um conhecimento básico da teoria dos conjuntos, como as relações e as principais operações entre eles (união, complemento, intersecção e diferença).
Antes de iniciar o estudo da teoria dos autômatos propriamente dita, é importante falar conceitualmente sobre as quatro gramáticas (Gramáticas com Estrutura de Frase, Gramáticas
Sensíveis ao Contexto, Gramáticas Livres de