Teoria da computação

Páginas: 7 (1547 palavras) Publicado: 29 de setembro de 2012
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
simonedp@fc.unesp.br
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 ateoria 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ísticasindispensá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 deformaçã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 complexidadecomputacional de um sistema. A
Máquina de Turing também é um reconhecedor.
Entre as linguagens existe uma ordem hierárquica chamada de Hierarquia de Chomsky (Figura 1). Noah
Chomsky definiu estas classes como potenciais modelos para as linguagens naturais. Nem sempre as
linguagens de programação são tratadas adequadamente nessa hierarquia. Existem linguagens que não são
livres de contexto, para asquais os formalismos sensíveis ao contexto são excessivos, sendo inadequados
principalmente no que se refere à complexidade computacional. Adicionalmente o conhecimento das
linguagens sensíveis ao contexto é relativamente limitado, o que dificulta o seu tratamento. (Menezes,
2000)

Figura 1. Hierarquia de Chomsky
A seguir tem uma tabela (Tabela 1) que traz uma correspondência entre asclasses de linguagens,
gramáticas e reconhecedores.

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

Página 2 de 7

Tabela 1. Linguagem, gramática e reconhecedor
Linguagem
Gramática
Tipo 0: Ling Enumeráveis Recursivamente
Tipo 1: Sensíveis ao Contexto
Tipo 2: Ling Livres deContexto
Tipo 3: Ling Regulares

Gramáticas Irrestritas
Gramáticas Sensíveis ao Contexto
Gramáticas Livres de Contexto
Gramáticas Regulares

Reconhecedor
Máquinas de Turing
Autômato Limitado Linearmente
Autômatos com Pilha
Autômatos Finitos

2. Alfabeto, Cadeias e Linguagens
Estamos acostumados com a noção de linguagens naturais como o Português, Inglês, etc. Uma definição
informal deuma linguagem poderia ser dada como sendo um sistema capaz de expressar idéias, fatos,
conceitos e que inclui um conjunto de símbolos e regras para sua manipulação. Ou ainda, defini-se
linguagem como o uso da palavra articulada ou escrita como meio de expressão e comunicação entre
pessoas. As definições são muitas, mas uma definição formal deve ser introduzida.
Definição 1.
Um alfabeto é um...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Teoria da computação
  • teoria da computação
  • Teoria da computação
  • Teoria da Computação
  • Teoria da Computaçao
  • teoria da computação
  • Teoria da computação
  • Teoria da computação

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!