Scribd
Carregar
3 visualizações14 páginas

Introdução aos Autômatos Finitos

Autômatos finitos são modelos matemáticos que representam sistemas computacionais com memória limitada, utilizados em controladores simples e reconhecimento de padrões. Eles são conhecidos como máquinas de estados finitos e podem ser determinísticos, onde cada símbolo do alfabeto leva a um único estado. A função de transição estendida permite calcular o estado ativo após processar uma cadeia de entrada a partir de um estado inicial.

Enviado por

natan cesario
Direitos autorais
© All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato PDF, TXT ou leia on-line no Scribd
3 visualizações14 páginas

Introdução aos Autômatos Finitos

Autômatos finitos são modelos matemáticos que representam sistemas computacionais com memória limitada, utilizados em controladores simples e reconhecimento de padrões. Eles são conhecidos como máquinas de estados finitos e podem ser determinísticos, onde cada símbolo do alfabeto leva a um único estado. A função de transição estendida permite calcular o estado ativo após processar uma cadeia de entrada a partir de um estado inicial.

Enviado por

natan cesario
Direitos autorais
© All Rights Reserved
Levamos muito a sério os direitos de conteúdo. Se você suspeita que este conteúdo é seu, reivindique-o aqui.
Formatos disponíveis
Baixe no formato PDF, TXT ou leia on-line no Scribd

LINGUAGENS

FORMAIS E
AUTÔMATOS
AUTÔMATOS FINITOS

Autômatos finitos são modelos matemáticos que representam sistemas


computacionais ou de processamento de informações.

São modelos computacionais com quantidade limitada (finita) de memória.

São utilizados em controladores simples e em reconhecimento de padrão


em dados.

Também chamados máquinas de estados finitos.


AUTÔMATOS FINITOS

Autômatos finitos são modelos matemáticos que representam sistemas


computacionais ou de processamento de informações.

São modelos computacionais com quantidade limitada (finita) de memória.

São utilizados em controladores simples e em reconhecimento de padrão


em dados.

Também chamados máquinas de estados finitos.

São dispositivos reconhecedores de linguagens: dada : ω E Σ*, aceita ω


se ω E L e rejeita caso contrário, sendo L a linguagem que ele foi projetado
para reconhecer.
AUTÔMATOS FINITOS DETERMINÍSTICOS
AUTÔMATOS FINITOS DETERMINÍSTICOS

Em geral são representados por um diagrama de estados.


AUTÔMATOS FINITOS DETERMINÍSTICOS

DEFINIÇÃO: Um autômato finito determinístico (AFD) é uma 5-upla


AUTÔMATOS FINITOS DETERMINÍSTICOS

Exemplo:

M = ({q1,q2,q3}, {0,1}, σ, q1, {q3}) em que σ é dada por

é um AFD
AUTÔMATOS FINITOS DETERMINÍSTICOS
Obs:

▪ Autômato: máquina automática

▪ Finito: com memória limitada (estados)

▪ Determinístico: para cada símbolo do alfabeto existe exatamente um


estado para o qual o autômato pode transitar a partir do único estado
ativo.
AUTÔMATOS FINITOS DETERMINÍSTICOS

Computação

Vamos computar as cadeias:

▪ 00110
▪ 010101
▪ 100
AUTÔMATOS FINITOS DETERMINÍSTICOS
Exercício:
Desenhe o diagrama do autômato A definido a seguir:
A = (Q;Σ, σ, p,{r}), tal que Q = {p, q, r}, Σ= {0;1} e a função σ é definida
abaixo:
σ (p,1) = p
σ (p,0) = q
σ (q,0) = q
σ (q,1) = r
σ (r,0) = r
σ (r,1) = r
AUTÔMATOS FINITOS DETERMINÍSTICOS
Exercício:
Desenhe o diagrama do autômato A definido a seguir:
A = (Q;Σ, σ, p,{r}), tal que Q = {p, q, r}, Σ= {0;1} e a função σ é definida
abaixo:
σ (p,1) = p
σ (p,0) = q Solução:

σ (q,0) = q
σ (q,1) = r
σ (r,0) = r
σ (r,1) = r
FUNÇÃO DE TRANSIÇÃO ESTENDIDA

Exercício:
DEFINIÇÃO: Seja M =(Q, Σ, σ, q0, F) um AFD. A função de transição
estendida de M é a função
definida da seguinte forma: para q E Q e ω E Σ*,

Ou seja: é o estado ativo em M após computar toda uma cadeia ω


a partir de estado q.
FUNÇÃO DE TRANSIÇÃO ESTENDIDA

Exemplo:

(q1, 1100) = q2

(q1, 001010) = q3
(q1, ε ) = q1

(q2, 0000) = q2

(q2, 1100) = q3
REFERENCIAS

Livro [1]

Você também pode gostar