Teoria da computação

Cursos:

Bacharelado em Ciência da Computação e
Bacharelado em Sistemas de Informação
Disciplinas: (1493A) Teoria da Computação e Linguagens Formais,
(4623A) Teoria da Computação e Linguagens Formais e
(1601A) Teoria da Computação
Professora: Simone das Graças Domingues Prado [e-mail] e-mail: home-page: wwwp.fc.unesp.br/~simonedp/discipl.htm

Apostila 01
Assunto:

Fundamentação da Teoria da Computação e
Linguagens Formais

Objetivos:

⇒

Introduzir conceitos fundamentais da disciplina

Conteúdo:
1. Introdução
2. Alfabetos, Cadeias e Linguagens

___________________________________________________________________________________________________
2º semestre de 2010. Simone Domingues Prado – Apostila 01

Página 1 de 7

1. Introdução

Estudar a teoria da computação providencia conceitos e princípios que ajudam a entender a natureza geral da computação. Para estudar esses princípios básicos constroem-se modelos de computadores abstratos para resolução de pequenos, mas não fúteis, problemas.
Para modelar o hardware de um computador é introduzido o conceito de autômatos. Um autômato é uma construção que possui todas as características indispensáveis de um computador digital: entrada, saída, armazenagem temporária, tomadas de decisão. Um autômato é um reconhecedor da linguagem. Através dos reconhecedores é possível identificar se a cadeia de símbolos pertence ou não a uma linguagem.
Linguagem formal é uma abstração das características gerais de uma linguagem de programação. Assim, possui um conjunto de símbolos, regras de formação de sentenças, etc.
Estudar computação do ponto de vista teórico é sinônimo de caracterizar o que é ou não é computável.
Para tanto, é preciso obter um modelo matemático que represente o que se entende por computação.
Existem vários modelos. Nessa disciplina será dado enfoque nas Máquinas de Turing. Com a Máquina de
Turing podem-se verificar os limites da computação e a complexidade