Definição formal, diagramas de transição de estados e exemplos interativos
Baseado em: Cassandras & Lafortune, "Introduction to Discrete Event Systems", 2ª Ed. — Seção 2.2.2
1. Definição Formal
Um autômato determinístico G é uma sêxtupla: G = (X, E, f, Γ, x₀, Xm) X = conjunto de estados ·
E = conjunto finito de eventos ·
f : X × E → X = função de transição (parcial) Γ : X → 2E = função de eventos ativos (Γ(x) = eventos com f definida em x) x₀ = estado inicial ·
Xm ⊆ X = estados marcados (aceitação/conclusão de tarefa)
O autômato começa em x₀ e, a cada evento e ∈ Γ(x), faz uma transição instantânea para f(x, e). Os estados marcados (círculos duplos) indicam conclusão de tarefa. O estado inicial é indicado por uma seta.
2. Exemplo 2.3 — Um Autômato Simples
O que ensina: Este exemplo introduz os conceitos fundamentais — como um autômato é representado por um diagrama de transição de estados. Mostra que f pode ser parcial (nem todo evento é possível em todo estado), que self-loops existem (f(x,a)=x) e que dois eventos distintos podem causar a mesma transição (f(z,a) = f(z,g) = y).
ESPECIFICAÇÃOE = {a, b, g} ·
X = {x, y, z} ·
x₀ = x ·
Xm = {x, z}
⚡ Interativo — clique nos eventos para navegar pelo autômato
Estado atual: x (inicial, marcado)
Cadeia: ε
3. Exemplo 2.4 — Linguagem Marcada
O que ensina: Mostra a diferença entre L(G) (linguagem gerada — todos os caminhos possíveis) e Lm(G) (linguagem marcada — caminhos que terminam em estado marcado). Aqui, f é total (todos os eventos definidos em todos os estados), então L(G) = E*. Mas Lm(G) = apenas cadeias que terminam com a.
ESPECIFICAÇÃOE = {a, b} ·
X = {0, 1} ·
x₀ = 0 ·
Xm = {1} L(G) = E* (tudo) ·
Lm(G) = { cadeias que terminam com a }
⚡ Interativo — observe como a marcação muda
Estado atual: 0 (inicial)
Cadeia: ε · Não marcado
4. Exemplo 2.6 — Autômatos Equivalentes em Linguagem
O que ensina: Múltiplos autômatos com estruturas completamente diferentes podem gerar e marcar as mesmas linguagens. Dois autômatos são equivalentes em linguagem se L(G₁) = L(G₂) e Lm(G₁) = Lm(G₂). Isso mostra que a representação não é única — o importante é o comportamento, não a estrutura interna.
O autômato abaixo é uma modificação do Exemplo 2.4: removemos o self-loop b no estado 0. Agora f(0,b) é indefinido, então L(G) ≠ E*. Cadeias com dois b's consecutivos não são possíveis.
⚡ Interativo — note que b no estado 0 está desabilitado
Estado atual: 0 (inicial) · Γ(0) = {a}
Cadeia: ε
5. Exemplo 2.7 — Bloqueio (Deadlock e Livelock)
O que ensina: Um autômato é bloqueante se L̄m(G) ⊂ L(G) (inclusão estrita). Isso acontece quando existe deadlock (estado sem transições de saída e não marcado) ou livelock (ciclo de estados não marcados sem saída). Aqui, o estado 5 é deadlock e os estados {3,4} formam um livelock.
ESPECIFICAÇÃOE = {a, b, g} ·
X = {0,1,2,3,4,5} ·
x₀ = 0 ·
Xm = {0, 2} Estado 5 = deadlock · Estados {3,4} = livelock
⚡ Interativo — tente alcançar os estados 5 (deadlock) ou 3-4 (livelock)