Aula 3 Autômatos Finitos Determinísticos e Não Determinísticos

1

ACH2043INTRODUÇÃO À TEORIA DA COMPUTAÇÃO

Aula 3

Autômatos Finitos Determinísticose Não Determinísticos

Profa. Ariane Machado Lima

2

Autômatos Finitos Determinísticos (AFD)

Dado um estado atual e um símbolo de entrada sabemos exatamente para onde ir (está determinado)

Note que para um AFD deve haver, saindo de cada estado, uma aresta para CADA símbolo do alfabeto

3

Exercício das aulas 1 e 2 - AFD Imagine um site de e-commerce em que:

– Há uma página “Inicial” de entrada

– Várias páginas “Intermediárias”

– as 5 últimas páginas para finalizar a compra são:

– Carrinho (visualização do conteúdo selecionado para compra)

– Endereço (seleção do endereço de entrega)

– Frete (seleção do tipo de envio)

– Pagamento (seleção do tipo de pagamento e pagamento propriamento dito)

– Fim (tela do “Parabéns por ter comprado conosco”)

Poderíamos modelar AF para isso? Como seria o seu “esquema gráfico”?

Vamos experimentar desenhar no JFLAP

4

Exercício das aulas 1 e 2 - AFD Imagine um site de e-commerce em que:

– Há uma página “Inicial” de entrada

– Várias páginas “Intermediárias”

– as 5 últimas páginas para finalizar a compra são:

– Carrinho (visualização do conteúdo selecionado para compra)

– Endereço (seleção do endereço de entrega)

– Frete (seleção do tipo de envio)

– Pagamento (seleção do tipo de pagamento e pagamento propriamento dito)

– Fim (tela do “Parabéns por ter comprado conosco”)

Poderíamos modelar AF para isso? Como seria o seu “esquema gráfico”?

Vamos experimentar desenhar no JFLAP Q

5

Exercício das aulas 1 e 2 - AFD Imagine um site de e-commerce em que:

– Há uma página “Inicial” de entrada

– Várias páginas “Intermediárias”

– as 5 últimas páginas para finalizar a compra são:

– Carrinho (visualização do conteúdo selecionado para compra)

– Endereço (seleção do endereço de entrega)

– Frete (seleção do tipo de envio)

– Pagamento (seleção do tipo de pagamento e pagamento propriamento dito)

– Fim (tela do “Parabéns por ter comprado conosco”)

PodQ?eríamos modelar AF para isso? Como seria o seu “esquema gráfico”?

Vamos experimentar desenhar no JFLAP Q

6

Exercício das aulas 1 e 2 - AFD Imagine um site de e-commerce em que:

– Há uma página “Inicial” de entrada

– Várias páginas “Intermediárias”

– as 5 últimas páginas para finalizar a compra são:

– Carrinho (visualização do conteúdo selecionado para compra)

– Endereço (seleção do endereço de entrega)

– Frete (seleção do tipo de envio)

– Pagamento (seleção do tipo de pagamento e pagamento propriamento dito)

– Fim (tela do “Parabéns por ter comprado conosco”)

PodQ?eríamos modelar AF para isso? Como seria o seu “esquema gráfico”?

Vamos experimentar desenhar no JFLAP Qq0F

7

Exercício das aulas 1 e 2 - AFD Imagine um site de e-commerce em que:

– Há uma página “Inicial” de entrada

– Várias páginas “Intermediárias”

– as 5 últimas páginas para finalizar a compra são:

– Carrinho (visualização do conteúdo selecionado para compra)

– Endereço (seleção do endereço de entrega)

– Frete (seleção do tipo de envio)

– Pagamento (seleção do tipo de pagamento e pagamento propriamento dito)

– Fim (tela do “Parabéns por ter comprado conosco”)

PodQ?eríamos modelar AF para isso? Como seria o seu “esquema gráfico”?

Vamos experimentar desenhar no JFLAP Qq0F

8

Exercício das aulas 1 e 2 - AFD Imagine um site de e-commerce em que:

– Há uma página “Inicial” de entrada

– Várias páginas “Intermediárias”

– as 5 últimas páginas para finalizar a compra são:

– Carrinho (visualização do conteúdo selecionado para compra)

– Endereço (seleção do endereço de entrega)

– Frete (seleção do tipo de envio)

– Pagamento (seleção do tipo de pagamento e pagamento propriamento dito)

– Fim (tela do “Parabéns por ter comprado conosco”)

PodQ?eríamos modelar AF para isso? Como seria o seu “esquema gráfico”?

Vamos experimentar desenhar no JFLAP Qq0F

9

Exercício das aulas 1 e 2 - AFD

– O que seria Σ ?

10

Exercício das aulas 1 e 2 - AFD

– O que seria Σ ?

– Σ = {produto, home, carrinho, end, calcular_frete, pagar, ok}produto, home, carrinho, end, calcular_frete, pagar, ok}}

11

Exercício das aulas 1 e 2 - AFD

– O que seria Σ ?

– Σ = {produto, home, carrinho, end, calcular_frete, pagar, ok}produto, home, carrinho, end, calcular_frete, pagar, ok}}

12

Exercício das aulas 1 e 2 - AFD

– O que seria Σ ?

– Σ = {produto, home, carrinho, end, calcular_frete, pagar, ok}produto, home, carrinho, end, calcular_frete, pagar, ok}}

– δ está correta para um AFD?

13

Exercício das aulas 1 e 2 - AFD

– O que seria Σ ?

– Σ = {produto, home, carrinho, end, calcular_frete, pagar, ok}produto, home, carrinho, end, calcular_frete, pagar, ok}}

– δ está correta para um AFD?• Q x Σ está completamente definido?

14

Exercício das aulas 1 e 2 - AFD

– O que seria Σ ?

– Σ = {produto, home, carrinho, end, calcular_frete, pagar, ok}produto, home, carrinho, end, calcular_frete, pagar, ok}}

– δ está correta para um AFD?• Q x Σ está completamente definido? AINDA NÃO

• Preciso completar essa TABELA:

15

Exercício das aulas 1 e 2 - AFD

– O que seria Σ ?

– Σ = {produto, home, carrinho, end, calcular_frete, pagar, ok}produto, home, carrinho, end, calcular_frete, pagar, ok}}

– δ está correta para um AFD?• Q x Σ está completamente definido? AINDA NÃO

• Preciso completar essa TABELA:

?

16

Exercício das aulas 1 e 2 - AFD

– O que seria Σ ?

– Σ = {produto, home, carrinho, end, calcular_frete, pagar, ok}produto, home, carrinho, end, calcular_frete, pagar, ok}}

– δ está correta para um AFD?• Q x Σ está completamente definido? AINDA NÃO

• Preciso completar essa TABELA:

Inicial ?

17

Exercício das aulas 1 e 2 - AFD

– O que seria Σ ?

– Σ = {produto, home, carrinho, end, calcular_frete, pagar, ok}produto, home, carrinho, end, calcular_frete, pagar, ok}}

– δ está correta para um AFD?• Q x Σ está completamente definido? AINDA NÃO

• Preciso completar essa TABELA:

Inicial Intermediária ?

18

Exercício das aulas 1 e 2 - AFD

– O que seria Σ ?

– Σ = {produto, home, carrinho, end, calcular_frete, pagar, ok}produto, home, carrinho, end, calcular_frete, pagar, ok}}

– δ está correta para um AFD?• Q x Σ está completamente definido? AINDA NÃO

• Preciso completar essa TABELA:

Inicial Intermediária ?Carrinho

19

Exercício das aulas 1 e 2 - AFD

– O que seria Σ ?

– Σ = {produto, home, carrinho, end, calcular_frete, pagar, ok}produto, home, carrinho, end, calcular_frete, pagar, ok}}

– δ está correta para um AFD?• Q x Σ está completamente definido? AINDA NÃO

• Preciso completar essa TABELA:

Inicial Intermediária Inválido Inválido Inválido InválidoCarrinho

20

Inicial Intermediária Inválido Inválido Inválido InválidoCarrinho

21

22

23

Exercício aula 2 – slide 27 – ex 2 Descreva o diagrama de estados de um AFD que aceita cadeias binárias (compostas

por 0’s e 1’s) que comecem e terminem com zero, com tamanho pelo menos 1

0, 00, 010, 000000, 0101110, ...

24

Exercício aula 2 – slide 27 – ex 2 Descreva o diagrama de estados de um AFD que aceita cadeias binárias (compostas

por 0’s e 1’s) que comecem e terminem com zero, com tamanho pelo menos 1

0, 00, 010, 000000, 0101110, ...

Simulação no JFlap

25

Qual a complexidade (tempo) de análise de uma cadeia por um AFD?

26

Qual a complexidade (tempo) de análise de uma cadeia por um AFD?

O(n) – n sendo o tamanho da cadeia de entrada

27

Qual a complexidade (tempo) de análise de uma cadeia por um AFD?

O(n) – n sendo o tamanho da cadeia de entrada

28

Exercício

Projete um AFD (diagrama de estados) que, dado Σ = {produto, home, carrinho, end, calcular_frete, pagar, ok}0,1,2,<RESET>}, aceita a cadeia de entrada se a soma dos RESET>}, aceita a cadeia de entrada se a soma dos números for igual a 0 módulo 3 (ou seja, se a soma for um múltiplo de 3). <RESET>}, aceita a cadeia de entrada se a soma dos RESET> zera o contador. Cadeia vazia também é aceita.

29

Exercício - solução

30

Autômatos finitos Pode ser mais conveniente projetar o autômato usando a

definição formal ao invés do diagrama de estados

Ex: generalização do autômato anterior para aceitar somas múltiplas de i, mantendo o mesmo alfabeto (linguagem Ai)

31

Autômatos finitos Pode ser mais conveniente projetar o autômato usando a

definição formal ao invés do diagrama de estados

Ex: generalização do autômato anterior para aceitar somas múltiplas de i, mantendo o mesmo alfabeto (linguagem Ai)

32

Autômatos Finitos Não Determinísticos (AFN)

Um estado pode ter 0 ou mais transições (setas saindo) para cada símbolo de Σ

Um estado pode ter setas rotuladas por ε ou λ (string vazia)

33

Autômatos Finitos Não Determinísticos (AFN)

Um estado pode ter 0 ou mais transições (setas saindo) para cada símbolo de Σ

Um estado pode ter setas rotuladas por ε ou λ (string vazia)

Como ficaria a função de transição neste caso???

34

Autômatos Finitos Não Determinísticos (AFN)

Σε = Σ U {produto, home, carrinho, end, calcular_frete, pagar, ok}ε}

Conjunto potência

35

Autômatos Finitos Não Determinísticos (AFN)

Que linguagem este AFN reconhece?

36

Autômatos Finitos Não Determinísticos (AFN)

Que linguagem este AFN reconhece?

Sequências binárias que contenham 11 ou 101

37

AFN como fica a tabela da função de transição

Ø ØØØ

Ø Ø

38

AFN como fica a tabela da função de transição

Exercício: que linguagem esse AFN descreve?

Ø ØØØ

Ø Ø

39

Funcionamento de um AFN

Sempre que o autômato se depara com um não-determinismo (símbolo repetido ou ε) faz uma cópia de si (um clone), exatamente no ponto onde pausou, e cada cópia segue com uma alternativa, em paralelo, a partir daquele ponto.

Se alguma cópia aceitar a cadeia, então o AFN aceita a cadeia

As várias cópias são como várias threads ou processos executados em paralelo...

40

Por causa do ε

Árvore decomputações

41

Por causa do ε

Árvore decomputações

42

Árvore decomputações

43

‘

Por causa do ε

Árvore decomputações

44

‘

Por causa do ε Como q2 tem uma transição no vazio,assim que ele é alcançado a transiçãoé feita sem consumir nenhum símbolo da entrada.

Note que é possível sair de q1 e ir paraq3, passando por q2, consumindo apenas o símbolo “1” da entrada. Mas, devido à restrição da função de transição δ(q2,1) = Ø, issosó pode ser feito se a transição no vazio for feita assim que o estado q2 for alcançado (δ(q2,ε) = {produto, home, carrinho, end, calcular_frete, pagar, ok}q3})

45

Por causa do ε

Árvore decomputações

46

Por causa do ε

Árvore decomputações

47

Por causa do ε

Árvore decomputações

48

Por causa do ε

Árvore decomputações

49

Por causa do ε

Árvore decomputações

50

Por causa do ε

Árvore decomputações

51

Por causa do ε

Árvore decomputações

52

Por causa do ε

Árvore decomputações

53

Por causa do ε

Árvore decomputações

54

Por causa do ε

Árvore decomputações

55

Por causa do ε

Árvore decomputações

56

Por causa do ε

Exercício: façam no papel e no JFlap a simulação para a entrada 1111

57

Logo, quem são mais eficientes? (em termos de tempo...)

58

Qual a complexidade (tempo) de análise de uma cadeia por um AFN?

59

Por causa do ε

O(n * |Q|)

Cada “nó” dessa árvore poderia ter no máximo |Q| filhos, e poderíamos descartar nós repetidos em um mesmo nível

Qual a complexidade (tempo) de análise de uma cadeia por um AFN?

60

Logo, quem são mais eficientes? (em termos de tempo...)

AFD’s são mais eficientes que AFN’s (tempo)

61

Exercício

Desenhe um AFN para a linguagem formada por sequências formadas apenas por zeros, mas que contenham o nr de zeros sendo um múltiplo de 2 ou múltiplo de 3

62

Exercício

Desenhe um AFN para a linguagem formada por sequências formadas apenas por zeros, mas que contenham o nr de zeros sendo um múltiplo de 2 ou múltiplo de 3

63

Exercício - Resposta

L = ?

64

Exercício - Resposta

L = {produto, home, carrinho, end, calcular_frete, pagar, ok} w | w є 0* e |w| = 2*i, i = 0, 1, …} U {produto, home, carrinho, end, calcular_frete, pagar, ok} w | w є 0* e |w| = 3*i, i = 0, 1, …}

65

Exercício

Desenhe um AFN para a linguagem formada por sequências binárias que contenham 1 na antepenúltima posição

Resolução no primeiro vídeo da aula 4

66

Lista de Exercícios do Sipser (2a ed)

Exercícios 1.1, 1.2, 1.3, 1.6 e 1.7

No 1.7:

* : 0 ou mais vezes

+ : 1 ou mais vezes

Ex: 1*(001+)*