kkhhjk

Prof. Rômulo Silva

Teoria da Computação
Maio/2007

1

Prof. Rômulo Silva

Objetivo desta apostila
Esta apostila foi desenvolvida com o objetivo de facilitar o entendimento da Teoria da
Computação, principalmente no que se refere às Linguagens Formais e Autômatos. Na sua elaboração foram utilizados os principais livros-textos adotados em disciplinas dessa área. Os exemplos apresentados são bastante simples, visando fins didáticos. Portanto, esta apostila NÃO substitui os livros-textos, sendo apenas um material auxiliar.
Se você tem sugestões e/ou correções, envie para [e-mail] .
Agradecemos antecipadamente.
Rômulo César Silva

2

Prof. Rômulo Silva

1. Introdução
Teoria da Computação. A Teoria da Computação abrange o estudo de modelos de computadores ou máquinas e o respectivo poder computacional destes modelos. Isto é, que classes de problemas podem ser resolvidas em cada modelo e como representá-los. O modelo de computação atual (ano base: 2007) é incapaz de entender a linguagem humana direta: seja falada ou escrita, dado o número enorme de possibilidades de significados e/ou acepções de uma mesma palavra, além das variações de construções de frases.
Linguagens Formais. Para diminuir este distanciamento entre a língua humana (por exemplo: o português, o inglês, etc.) e a programação de computadores foram criadas as linguagens de programação. Estas são linguagens formais, isto é, procuram eliminar toda ambigüidade possível, garantindo assim que um comando e palavras reservadas tenham sempre o mesmo significado independentemente de onde apareçam no programa.
A língua portuguesa é uma linguagem natural, sendo que sua representação escrita possui uma gramática. Esta indica onde se deve usar preposição ou não; a concordância verbal e nominal, entre outras regras.
Gramáticas. Da mesma forma, as linguagens de programação possuem uma gramática associada, que define a formação de programas válidos. Por exemplo: se