Teoria da

computaçãoAula 06

Autômatos

Prof. Marcos Devaner.

Os autômatos finitos, também

conhecido como máquina de

estados são bons modelos para

computadores com uma

quantidade de memória

extremamente limitada. Podemos

ver estes tipos de computador em

nosso dia a dia em vários dispositivos

eletrômecânicos como por exemplo

o controlador de uma porta

automática.

1. autômato

Aula 06 – autômatos

Um autômato finito tem várias partes:

1. Possui um conjunto de estados.

2. Regras para ir de um estado para o outro, dependendodo simbolo de entrada.

3. Possui um alfabeto de entrada que indica o simbolos deentrada permitidos.

4. Tem um estado inicial.

5. Um ou mais estados de aceitação.

Em linguagem matemática, uma ista de 5 elementos échamado de 5-upla, com isto, podemos diser que umautômato finito é um 5-upla composto por estas cinco partes.

2. Função de transição

Aula 06 – autômatos

Esta denominação é usada para definir regras demovimentação de um estado para o outro. Esta função é

representada pelo simbolo δ.

Exemplo:

Este exemplo mostra un função de tranasição em que se o

autômato está no estado q1 e lê o simbolo 1 ele se move para o

estado q2. Isto também pode ser mostrado da seguinte forma:

δ(q1,1)= q2.

3. Definição formal

Aula 06 – autômatos

Um autômato finito é um 5-upla (Q, ∑, δ, q0, F), onde

1. Q: é um conjunto finito de estados

2. ∑: é um conjunto finito chamado de alfabeto

3. δ : é Q x ∑ (função de transição).

4. Q0 : é o estado inicial e pertence a Q.

5. F esta contido em Q é o conjunto de estados de

aceitação.

4. Descrição formal

Aula 06 – autômatos

Dado o autômato chamado de M1.

Descrição formal

1. Q= {q1,q2},

2. ∑ ={0,1}

3. δ =

1. Q0 = q1

2. F = q2

0 1

q1 q1 q2

q2 q1 q2

Testando este exemplo, você irá perceber que M1 aceita todas as

cadeias que terminam em 1. Podemos descrever da seguinte forma:

L (M1) ={w| w termina com um 1}, onde w são as cadeias aceitas

por M1 .

Obrigado!Saiba mais em: www.integrar-online.blogspot.com

Fim