Aula 04 - Autômatos Finitos Determinísticos.pdf

8/18/2019 Aula 04 - Autômatos Finitos Determinísticos.pdf

1/24

CENTRO UNIVERSITÁRIO DE ENSINO SUPERIOR DO ESTADO DO AMAZONAS

Aula 04Máquinas de Estado Finito(Autômatos Finitos Determinísticos)

Fontes principais:- Newton Vieira. Introdução aos Fundamentos da Computação – Linguagens eMáquinas. Pioneira Thomson Learning, 2006;- Thomas A. Sudkamp. Languages and Machines. 3rd edition. Pearson, 2006

Prof. André Alves Nogueira, MSc.

2015 1


2/24


2

Exemplo de Sistema de Estados Finitos

• Um homem, um leão, um coelho e um repolho devematravessar um rio usando uma canoa

• Restrições:• o homem deve transportar no máximo um dos três de

cada vez de uma margem à outra;• o leão não pode ficar na mesma margem que o coelho

sem a presença do homem;•

o coelho não pode ficar com o repolho sem a presençado homem

• É possível executar a travessia de modo que o coelho nem orepolho sejam comidos?


3/24


3


• Representação do exemplo como um diagrama de estados:• um grafo dirigido que modela o espaço de estados (vértices) e

transições (arestas), com estados inicial e final destacados

•

estados:• cada estado representa o conjunto dos que estão na margemesquerda (o complemento do conjunto está na margem direita)

• supõe-se que no início todos estão na margem esquerda• h representa “homem”, l representa “leão”, etc.

• transições:• se existe uma aresta com rótulo “a” do estado para o estado 2,

diz-se que há uma transição de para 2 sob “a”• s representa o homem atravessa sozinho; l representa o homem

atravessa levando o leão; c, levando o coelho; etc.


4/24


4


• Representação do exemplo como um diagrama de estados:


5/24


5


• Uma sequência de movimentações de uma margem à outrapode ser representada por uma palavra sobre {s, l, c, r}*

• Um problema modelado desta maneira pode ser visto como:• encontrar uma palavra que represente uma sequência de

transições que leve de um estado inicial a um estadofinal

•

no exemplo:• estado inicial: {h, l, c, r }; estado final: {}• infinitas soluções sendo duas de tamanho mínimo:

cslcrsc e csrclsc


6/24


6


• Dada uma palavra w de {s, l, c, r}*, w é uma solução se seu“caminho correspondente” partindo do estado inicial chegaao estado final, i.e.:

• w pode ser processada da esquerda para a direita,símbolo a símbolo até o último

• se o estado alcançado pertence ao conjunto de estados

finais, diz-se que w é reconhecida ou aceita• senão, diz-se que w não é reconhecida ou é rejeitada


7/24


7

Atividade Extra – Valendo 1 ponto

• Tem três jesuítas e três canibais estão do lado esquerdo do rioe precisam atravessar de barco para o outro lado.

• Restrições:• O barco só pode levar duas pessoas;• Os jesuítas não podem ficar em menor número em

nenhuma das margens, porque os canibais devoram osjesuítas;

• É necessário que haja mais jesuítas ou um numero igual.

1- Como eles irão atravessar??????? Faça um esquema mostrandoas duas margens.

2- Faça o diagrama de estados representando apenas o lado

esquerdo da margem.


8/24


8

Atividade Extra

• Representação do exemplo 2 como um diagrama de estados:

JJJCCCB

JJJC

JJCC

X

D

X

D

JJJCCB

C

C

JJJ

JJ

X

X JJJCB

C

C

JC

Y

Y

JJCCB

D D

CC

Y

Y

CCCB

C

CC X

XCCB

C

C

{ } X

X

C – 1 canibalJ – 1 jesuítaD – 1 canibal e 1 jesuítaX – 2 canibaisY – 2 jesuítas

JCB JJ

D

D


9/24


9

Autômatos Finitos• O diagrama de estados representa uma máquina de estados

finitos do tipo reconhecedora de linguagens, ou um autômato finito

• duas saídas possíveis: aceitação ou rejeição da entrada

• Seja w = xy . No reconhecimento de w , tendo x processada, énecessária para continuação do processo apenas umaconfiguração instantânea composta de:

• o estado atual e y

• O estado atual é a única “memória” do sistema: condensa oprocessamento já ocorrido do prefixo da palavra ejuntamente com y (ainda não processada) determina ocomportamento subsequente da máquina

• ex.: mecanismo de controle de um elevador


10/24


10

Autômatos Finitos e Linguagens• O conjunto de todas as soluções (de um problema sobre um

sistema de estados finitos) é o conjunto das palavrascorrespondentes aos caminhos do estado inicial ao final,onde:

•

cada palavra é formada concatenando-se os rótulos dasarestas percorridas

• Assim, um autômato finito define uma linguagem:• o conjunto de todas as palavras que rotulam os caminhos

do estado inicial ao estado final, i.e., as palavrasreconhecidas pelo autômato


11/24


11

Características do exemplos• Características comuns a autômatos finitos

• o número de estados é finito

• Características comuns a autômatos finitos determinísticos•

Para cada par (estado, símbolo) existe no máximo umatransição, i.e.:

• se existe uma transição do estado para 2 soba, então não existe outra transição de para

qualquer outro estado sob a; ou ainda

• dada uma palavra w , existe um único estado quepode ser atingido a partir de qualquer estado,processando-se w


12/24


12

Características do exemplos• Características específicas do exemplo:

• a toda transição de um estado para um estado 2corresponde uma transição inversa sob o mesmo símbolo

• existe um único estado final


13/24


13

Autômatos Finitos Determinísticos• Um Autômato Finito Determinístico (AFD) é uma estrutura

matemática constituída de 3 tipos de entidades:• um conjunto de estados• um conjunto de transições•

um alfabeto

• Def.: um AFD é uma quíntupla (E , Σ, δ, i, F ), onde:• E é um conjunto finito de um ou mais estados• Σ é um alfabeto• δ: E x Σ → E é a função de transição, uma função total• i ∈ E é o estado inicial• F ⊆ E é o conjunto de estados finais

Á


14/24


14

AFD – Função de transição• Função de transição δ : E x Σ → E

• δ é uma função total, logo há exatamente um estadopara cada par (e, a), e ∈ E , a ∈ Σ:

• determinismo de um AFD

Á


15/24


15

AFD – Função “Resulta em”• Em qualquer ponto do processamento de uma palavra, seu

reconhecimento só depende da configuração instantânea[,w ], onde é o estado corrente e w ∈ Σ* é o sufixo aindanão processado da palavra:

• [, aw ] ⊢ [, w ] denota que a configuração [, w ] éalcançada a partir de [, aw ] através de uma transiçãodo autômato

• Def.: A função de ⊢ E x Σ+ para E x Σ*, que leva de umaconfiguração instantânea, a outra, é definida como:

• [, aw ] ⊢ [δ(, a), w ]• para a ∈ Σ e w ∈ Σ*, onde δ é a função de transição do

autômato

Á


16/24


16

AFDs - Exemplo• Assim, formalmente, o autômato do exemplo da travessia dorio é a quíntupla: (E , {s,l,c,r}, δ, {h, l, c, r }, {{}}), onde:

• E = {{h, l, c, r }, {l, r }, {h, l, r }, {l}, {r }, {h, l, c}, {h, c, r },{c}, {h, c}, {}, t}

• δ é dada pela tabela de transição:

Á


17/24


17

Á


18/24


18

AFDs - Exemplo

δ 0 1

0 0 1

1 2 3

2 4 5

3 0 1

4 2 3

5 4 5

Ex. 3: Seja o autômato ({0, 1, 2, 3, 4, 5}, {0, 1}, δ, 0, {0}), quedetermina se um número binário é divisível por 6, sendo δ dadapor:

Construa o diagrama de estados correspondente

C RO RS ÁR O D S O S P R OR DO S ADO DO A A O AS


19/24


19

AFDs - Exemplo

δ 0 1

0 0 1

1 2 3

2 4 5

3 0 1

4 2 3

5 4 5

Ex. 3: Resolução:

0

1 2

3 4

5

10

0

1

1

0

0

1

0

1 0

1



20/24


20

Diagrama de Estados Simplificado• Para um diagrama de estados simplificado, assume-se quecaso alguma transição de algum estado e sob algum símbolo a

não esteja no diagrama, então existe um estado de erroimplícito e' tal que:

• existe uma transição de e para e' sob a• e' não é estado final• existe um transição de e' para e' sob cada símbolo do

alfabeto

• OBS.: se e' é alcançado após o processamento de um prefixode uma palavra, então para qualquer sufixo a ser processadoa palavra não será reconhecida



21/24


21

Função de Transição Estendida

Def. 2: Seja um AFD M = (E , Σ, δ, i, F ). A função de transiçãoestendida para M, é uma função de E x Σ* para E , definidarecursivamente como:

(a) (e, λ ) = e;(b) (e, ay ) = ((e, a), y ), para todo a ∈ Σ e y ∈ Σ*

Ex.: Processamento da palavra 1010 pelo autômato do ex. 3:(0,1010) = ((0,1),010) por (b)

= (1,010) pois (0,1) = 1

= ((1,0),10) por (b)

= (2,10) pois (1,0) = 2= ((2,1),0) por (b)

= (5,0) pois (2,1) = 5

= ((5,0), λ ) por (b)

= (4, λ ) pois (5,0) = 4= 4 por (a)

δ 0 1

0 0 1

1 2 3

2 4 5

3 0 1

4 2 3

5 4 5



22/24


22

Atividade 41. Construa um autômato que aceita números binários divisíveis pordois.2. Construa um autômato que aceita strings de tamanho par sobreo alfabeto {a, b}.

3. Construa um autômato que aceita strings que iniciam com “0”

(zero) sobre o alfabeto {0, 1}.4. Construa um autômato que aceita strings que terminam com “1”(um) sobre o alfabeto {0, 1}.

5. Construa um autômato que aceita números binários divisíveis portrês.

6. Construa um autômato que aceita números binários divisíveis porquatro.

7. Construa um autômato que aceita números binários divisíveis porcinco.

0 - 01 - 12 - 103 - 114 - 100

5 - 1016 - 1107 - 1118 - 10009 - 100110 - 101011 - 1011

12 - 110013 - 110114 - 111015 - 111116 - 1000017 - 1000118 - 10010

19 - 1001120 – 1010021 – 1010122 – 1011023 – 1011124 - 11000



23/24


23

8. Construa um AFD que aceita a linguagem L sobre o alfabeto {0,1} cujosstrings possuem tamanho múltiplo de 3 ou terminam com 1.

9. Construa um AFD que aceita a linguagem L sobre o alfabeto {0,1} cujosstrings começam com 0 e terminam com 10 ou com 11

10. Construa um autômato que aceita a linguagem expressa por 03120| n ϵ

IN.11. O conjunto dos strings sobre {a, b, c} na qual todos os a’s precedem osb’s, que por sua vez precedem os c’s. É possível que não haja a’s, b’s ou c’s.

12. O conjunto dos strings sobre {a, b, c} com comprimento maior que três.

13. (0+1)*(00+11)(0+1)*14. (0+1)*01(11)*

15. Construa um autômato que aceite strings sobre {0,1} em que a quantidadede “a” é par e a quantidade de “b” é ímpar.

Atividade 4



24/24


24

Linguagem Reconhecida por um AFD

Def.: A linguagem reconhecida (aceita) por um AFD M = (E , Σ, δi, F ) é o conjunto L(M) = {w ∈ Σ* | (i, w ) ∈ F }

Exercício: Considere os seguintes diagramas de estado querepresentam autômatos finitos. Descreva os autômatosformalmente e diga que linguagens eles reconhecem

Documents

Aula 04 - Autômatos Finitos Determinísticos.pdf