af.org

Autômatos Finitos (Deterministas ou não)

1 Construindo um analisador léxico

Na ordem, de cima para baixo

• Em parênteses: técnica de conversão

Várias definições de ER

(Algoritmo de Thompson) \linebreak

Vários AFND

(Concatenção com ligações vazias) \linebreak

Um único AFND

(Algoritmo de Subconjuntos) \linebreak

Um único AFD

(Gerador de código) \linebreak

Função em uma linguagem de usuário

2 Diagramas de Transição

• Coleção de nós que representam estados
• Arestas entre estados, rotulada por um ou mais símbolos

Convenções

• Estados de \alert{aceitação} (ou finais)
• Estados de \alert{aceitação com *}
• Estado \alert{inicial}

Exemplo, supondo

identificador

→

letra (letra | digito)

Exemplo, supondo

relop

→

< | > | <= | >= | = | <

3 Definição de Autômato Finito

Autômato finito M sobre alfabeto Σ é (K, Σ, δ, e0, F)

K é um conjunto finito de estados

Σ é o alfabeto de símbolos da linguagem

δ : K × Σ → K é a função de transição de estados, parcial

e0 é o estado inicial

F é o conjunto de estados finais

4 Exemplo de Autômato Finito

Autômato que reconhece números reais e inteiros

4.1 Definição

$M = (K, Σ, δ, e0, F)$

• $Σ = \{ d, . \}$
• K = (e_0, e_1, e_2, e_3)
• F = (e_1, e_3)
• δ(e_0, d) = e_1
• δ(e_1, d) = e_1
• δ(e_1, .) = e_2
• δ(e_2, d) = e_3
• δ(e_3, d) = e_3

4.2 Tabela de Transições

	d	.
e_0	e_1
e_1	e_1	e_2
e_2	e_3
e_3	e_3

5 Segundo Exemplo de Autômato Finito

		a	b
inicial	q_0	q_1	q_2
	q_1	q_0	q_2
final	q_2	q_2	q_2

Este autômato corresponde a qual expressão regular?

6 Dois tipos de autômatos: AFD e AFND

• Autômato Finito Não-Determinístico (AFND)
  • Tem um conjunto de estados S
  • Funções de transição
  • Um estado de partida
  • Um conjunto de estados finais (de aceitação)

• Autômato Finito Determinístico (AFD)
  • Como um AFND
  • Não tem transições vazias
  • No máximo uma transição de saída por símbolo

7 Construção de Thompson

Expressão Regular → AFND

• Cada ER básica se traduz em um AFND
• Pode-se agregar os AFND conforme se agregam as ERs

Cada AFND tem exatamente um estado de partida e um estado final

Referências:

• https://en.wikipedia.org/wiki/Thompson’s_construction

8 Reconhecedores básicos

AFND para reconhecer $\bf\epsilon$

AFND para reconhecer um símbolo a

9 Reconhecedor de Alternativa

AFND que reconhece a alternativa a|b

10 Reconhecedor de Concatenação

AFND que reconhece a alternativa ab

11 AFND reconhecedor do Fechamento de Kleene

AFND que reconhece a*

Reflexão: tem um equívoco de abstração excessiva nesta solução!

• Qual é o equívoco?

12 Exercício

Construir um AFND que reconheça (a|b)*abb

13 Qual o problema de AFND?

Pontos positivos

• Bastante poderoso para implementar ERs
• Aplicação trivial: ERs → AFNDs → Full AFND (léxico)

Pontos negativos (Problema)

• ε-transições
• Várias transições de saída com o mesmo símbolo

• Fácil para a fase de projeto, difícil de implementar