Máquinas de estado finitas

Máquinas que "lembram" apenas o estado atual

Imagine um semáforo: ele não precisa saber quantas vezes já ficou vermelho, nem que horas são — só precisa saber em qual estado está (vermelho, amarelo, verde) e qual símbolo chegou (temporizador disparou, sensor de pedestres ativou). Esse é um autômato finito determinístico (DFA).

Formalmente, um DFA é uma 5-upla (Q, Σ, δ, q₀, F): estados Q, alfabeto Σ, função de transição δ: Q×Σ → Q, estado inicial q₀ e estados de aceitação F. A linguagem reconhecida pelo DFA é o conjunto de strings que o levam a um estado em F.

DFA para strings com número par de 1s

Digite uma string binária e avance passo a passo. O estado ativo é destacado no diagrama. q₀ (duplo círculo) é aceitador — a string é aceita se terminar aqui.

DFA em Python

# Máquina de estados finitos em Python
# DFA para strings binárias com número par de 1s

transitions = {
    "q0": {"0": "q0", "1": "q1"},  # par (aceitador)
    "q1": {"0": "q1", "1": "q0"},  # ímpar
}
accept_states = {"q0"}

def run_dfa(string):
    state = "q0"  # estado inicial
    for ch in string:
        state = transitions[state][ch]
    return state in accept_states

# Testes
run_dfa("1100")   # True  — dois 1s
run_dfa("1101")   # False — três 1s
run_dfa("")       # True  — zero 1s (par)
run_dfa("11")     # True  — dois 1s

FSM na prática: tokenizador com regex

# Tokenizador numérico usando FSM
# Reconhece: inteiros, floats, e o ponto isolado como erro

import re

# 'states' implícitos via regex — equivalente a uma FSM
TOKEN_RE = re.compile(r"""
    (?P<FLOAT>   d+.d*)   |   # 3.14, 3.
    (?P<INT>     d+)        |   # 42
    (?P<SPACE>   s+)        |   # espaços (ignorar)
    (?P<ERROR>   .)              # qualquer coisa inesperada
""", re.VERBOSE)

def tokenize(src):
    for m in TOKEN_RE.finditer(src):
        kind = m.lastgroup
        if kind != "SPACE":
            yield kind, m.group()

# Por baixo: o motor de regex compila o padrão para uma NFA,
# depois converte para DFA via construção de subconjuntos.
# Cada re.compile() é literalmente uma FSM compilada.

Construindo FSMs

Mini projeto: implemente a FSM para reconhecer identificadores válidos de Python: começam com letra ou underscore, seguidos de letras, dígitos ou underscores. Represente os estados como strings e a tabela de transição como dicionário. Teste com "nome_var", "_x1", "2errado", "ok".

Projeto principal: implemente um lexer completo para uma linguagem mini (inteiros, floats, operadores, identificadores, strings entre aspas) usando uma tabela de transição explícita — sem usar re. Compare a velocidade com a versão regex para arquivos grandes.

Desafio extra: implemente o algoritmo de Thompson para converter uma expressão regular para NFA, depois o algoritmo de subconjuntos para converter NFA para DFA, e finalmente o algoritmo de Hopcroft para minimizar o DFA. Teste que o DFA resultante é equivalente à regex original para pelo menos 100 strings aleatórias.

Teste sua intuição

Onde você encontra isso