Teoria da computação – Introdução

Olá amigos, estarei tirando um pouco do meu tempo para estar passando um pouco do estou aprendendo sobre “Teoria da Computação“. O livro que estarei seguindo se chama Uma Introdução à Teoria da Computação de  Michael Sipser. Esse livro pode ser facilmente adquirido na biblioteca de sua instituição de ensino.

Teoria da computação é uma disciplina onde você estará trabalhando fortemente o raciocínio lógico e computacional. Vamos iniciar com Teoria dos autômatos.

Segundo o livro de Michael Sipser são propriedades de modelos matemáticos de computação.

Autômato finito: Usado para processamento de texto, compiladores e projeto de hardware.
Gramática Livre de Contexto: usada em linguagens de programação.

Ideal para se começar a estudar a teoria da computação.

Definições:

Símbolo – letras e/ou dígitos
Alfabeto – Conjunto finito de símbolos
Ex.:
Σ = { 0,1,2,…,9}
Σ = {a,b,c,…,z}
Σ  = {0,1 }
Cadeia (string) (sobre Σ): qualquer sequência finita de elementos de Σ.
Ex.:
Σ= { a,b }
aabab, bb, abab

Tamanho de uma Cadeia x é o número de símbolos em x.

Notação:  | x |
Ex.:
| aabab | = 5
| abab | = 4

Cadeia Vazia : ε ou λ
| λ | = 0
a^n   Significa uma cadeia de a‘s de tamanho n.

Ex.:
a5 = aaaaa
a^1 = a (A elevado a um)
a^0 = λ   (Elevado a zero)

Continua na próxima publicação, onde entrarei em diagrama de estados. Fiquem com Deus!