31
Ling. Formais e Autômatos Autômatos finitos

Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Embed Size (px)

Citation preview

Page 1: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Ling. Formais e Autômatos

Autômatos finitos

Page 2: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Na aula de hoje...

Introdução

AF Determinístico

AF Não-determinístico

Equivalência entre AFD e AFN

Autômatos finitos

Page 3: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

1. Introdução

Um Autômato Finito é um sistema de estados finitos, o qual constitui um modelo computacional seqüencial Modelo matemático de um sistema, com

entradas e saídas discretas

estado

estímuloexterno

Page 4: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Exemplo

Travessia do rio Um grupo formado por um homem, um lobo,

uma cabra e um repolho, posicionados do lado esquerdo da margem de um rio. O problema consiste em transportá-los para a margem direita.

• existe um barco com capacidade para transportar somente o homem e um dos outros três elementos do grupo

• o lobo e a cabra não podem ficar sozinhos no mesmo lado

• a cabra e o repolho também não podem ficar sozinhos

Page 5: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Exemplo

H

L

C

R

Page 6: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Exemplo

HLCR/ ─ LR/HC HLR/C

R/HLC L/HCR

HCR/L HLC/R

C/HLR

HC/LR ─/HLCR

HC

HC

H

H

HR HR

HC HC

HLHL

HH

HC

HC

HL HL

HC HC

HRHR

H: homemL: loboC: cabraR: repolho

HÁ INFINITASSOLUÇÕES PARA

O PROBLEMA!

Page 7: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Autômato Finito Determinístico

Definição O autômato finito determinístico é aquele que

se encontra em um único estado depois de ler uma seqüência qualquer de entradas

O termo “determinístico” se refere ao fato de que, para cada entrada, existe um e somente um estado ao qual o autômato pode transitar a partir de seu estado atual

q0

q2q1

a b

Page 8: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Autômato Finito Determinístico

Definição Um autômato finito determinístico consiste

em:• Um conjunto finito de estados: Q• Um conjunto finito de símbolos de entrada: Σ• Uma função de transição que toma como

argumentos um estado e um símbolo de entrada, e retorna um estado: δ

• Um estado inicial (que está em Q)• Um conjunto de estados finais F (F é um

subconjunto de Q)

Page 9: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Autômato Finito Determinístico

Notação:

A = (Q, Σ, δ, q0, F)

Page 10: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Exemplo 1

L = { w | w é uma seqüência de 0’s e 1’s, com número par de 0’s e de 1’s }

Como seria o AFD que aceita essa linguagem?

Page 11: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Exemplo 1

L = { w | w é uma seqüência de 0’s e 1’s, com número par de 0’s e de 1’s }

P0P1 P0I1

I0P1 I0I1

1

1

1

1

0000

Page 12: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Exemplo 2

L = { w | w é um número binário múltiplo de 3 }

Como seria o AFD que aceita essa linguagem?

Page 13: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Exemplo 2

L = { w | w é um número binário múltiplo de 3 }

Resto0

Resto1

Resto2

1

1

0

0

1

0

Esse AFD aceita cadeia vazia - ε

Page 14: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Exemplo 2

L = { w | w é um número binário múltiplo de 3 }

Resto0

Resto1

Resto2

1

1

0

0

1

0

Esse AFD não aceita cadeia vazia - ε

Início

0

1

Page 15: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Linguagem de um AFD

A linguagem de um AFD A = (Q, Σ, δ, q0, F) é denotada por L(A) e definida por:

L(A) = { w | δ(q0, w) está em F }^

Page 16: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Autômato Finito Não-determinístico

Definição O autômato finito não-determinístico pode

estar em vários estados ao mesmo tempo• Capacidade de “adivinhar” algo sobre sua entrada

O AFN aceita as mesmas linguagens aceitas por um AFD

• São mais sucintos e mais fáceis de projetar

q0

q2q1

a a

Page 17: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Autômato Finito Não-determinístico

Definição Um autômato finito não-determinístico

consiste em:• Um conjunto finito de estados: Q• Um conjunto finito de símbolos de entrada: Σ• Uma função de transição que toma como

argumentos um estado e um símbolo de entrada, e retorna um subconjunto de Q: δ

• Um estado inicial (que está em Q)• Um conjunto de estados finais F (F é um

subconjunto de Q)

Page 18: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Autômato Finito Não-determinístico

Notação:

A = (Q, Σ, δ, q0, F)

Page 19: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Exemplo

L = { w | w aceita todas as strings que terminam em 01 }

Como seria o AFN que aceita essa linguagem?

Page 20: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Exemplo

L = { w | w aceita todas as strings que terminam em 01 }

q0 q1 q2

0

0, 1

1

O fato de outras escolhas usando os símbolos de entrada de w levarem a um estado de não-aceitação ou não levarem a nenhum estado em absoluto (a seqüência de estados “morre”), não impede w de ser aceito pelo AFN como um todo,

Page 21: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Exemplo

L = { w | w aceita todas as strings que terminam em 01 }

q0 q0 q0 q0 q0 q0

q1 q1 q1

q2 q2

0 0 1 0 1

paralisado

paralisado

q2 é um estado de aceitação, então 00101 é aceito!

Page 22: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Linguagem de um AFN

A linguagem de um AFN A = (Q, Σ, δ, q0, F) é denotada por L(A) e definida por:

L(A) = { w | δ(q0, w) ∩ F ≠ Ø }^

Page 23: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Equivalência entre AFD e AFN

Introdução Toda linguagem que pode ser descrita por um

AFN também pode ser descrita por um AFD Na prática, um AFD tem quase tantos estados

quanto os que o AFN tem, embora com freqüência tenha mais transições

No pior caso, o menor AFD pode ter 2n estados, enquanto o menor AFN para a mesma linguagem tem apenas n estados

Page 24: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Exemplo

L = { w | w aceita todas as strings que terminam em 01 }

q0 q1 q2

0

0, 1

1

0 1

{q0} {q0,q1} {q0}

{q1} ─ {q2}

{q2} ─ ─*

Page 25: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Exemplo

L = { w | w aceita todas as strings que terminam em 01 }

q0 q1 q2

0

0, 1

1

Como o conjunto de estados é {q0, q1, q2}, a construção de subconjuntos produz um AFD com 23 = 8 estados

Page 26: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Exemplo

q0 q1 q2

0

0, 1

1

0 1

{q0} {q0,q1} {q0}

{q1} ─ {q2}

{q2} ─ ─

{q0,q1} {q0,q1} {q0,q2}

{q0,q2} {q0,q1} {q0}

{q1,q2} ─ {q2}

{q0,q1,q2} {q0,q1} {q0,q2}

*

*

*

*

O oitavo estado, que não aparece na lista, seria o estado

Ø

Page 27: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Exemplo

q0 q1 q2

q0q1 q0q2 q1q2q0q1q2

0

1

1

0

1

0

11

0

1

Page 28: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Exemplo

q0 q1 q2

q0q1 q0q2 q1q2q0q1q2

0

1

1

0

1

0

11

0

1

De todos os estados listados, só podemos acessar os estados {q0}, {q0q1} e {q0q2}. Os estados inacessíveis não precisam constar. Portanto...

Page 29: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Exemplo

q0 q0q1 q0q2

0 1

1 0

0

1

Page 30: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Na próxima aula...

AF com ε-transições

Expressões regulares

Introdução

Operadores

Page 31: Ling. Formais e Autômatos Autômatos finitos. Na aula de hoje... Introdução AF Determinístico AF Não-determinístico Equivalência entre AFD e AFN Autômatos

Universidade Federal de São Carlos

Sérgio Donizetti Zorzo

[email protected]

Paulo R. M. Cereda

[email protected]