Capítulo 2 — Linguagens e Autômatos

§2.2 a §2.5 — Autômatos, Operações, Observadores e Linguagens Regulares

Resumo com todos os exemplos 2.3–2.23 resolvidos e diagramas de transição

Baseado em: Cassandras & Lafortune, "Introduction to Discrete Event Systems", 2ª Ed. — pp. 60–102

estado inicial

estado marcado

deadlock

livelock

a evento

1. Fundamentos — Autômato e suas Linguagens

G = (X, E, f, Γ, x₀, X_m) — X estados · E eventos · f : X × E → X transição (parcial!) · Γ(x) eventos ativos em x · x₀ inicial · X_m marcados.
Extensão a cadeias: f(x, ε) = x e f(x, se) = f(f(x, s), e).

L(G) = {s ∈ E* : f(x₀, s) definida} — linguagem gerada (todos os caminhos; sempre prefixo-fechada).
L_m(G) = {s ∈ L(G) : f(x₀, s) ∈ X_m} — linguagem marcada (caminhos que concluem a tarefa; não precisa ser prefixo-fechada).

Ex. 2.3 Um autômato simples

Fig. 2.1 — autômato do Exemplo 2.3

E = {a, b, g} · X = {x, y, z} · x₀ = x · X_m = {x, z}

RESOLVIDO Três observações do livro: (i) um evento pode não mudar o estado — f(x,a) = x (self-loop); (ii) dois eventos distintos podem causar a mesma transição — f(z,a) = f(z,g) = y, ou seja, observando apenas a transição z→y não distinguimos a de g; (iii) f é parcial — f(x,b) e f(y,g) não são definidas.

Conjuntos de eventos ativos: Γ(x) = {a, g} · Γ(y) = {a, b} · Γ(z) = {a, b, g}.
Aplicando f estendida (basta seguir o diagrama):
• f(y, ε) = y
• f(x, gba) = f(f(f(x,g),b),a) = f(f(z,b),a) = f(z,a) = y
• f(x, aagb) = f(f(f(f(x,a),a),g),b) = f(f(x,g),b) = f(z,b) = z
• f(z, bⁿ) = z para todo n ≥ 0 (self-loop b em z).

Ex. 2.4 Linguagem marcada

Dado E = {a, b}, queremos marcar L = {a, aa, ba, aaa, aba, baa, bba, …} — todas as cadeias de a's e b's terminadas em a.

Fig. 2.2 — autômato do Exemplo 2.4

X = {0, 1} · x₀ = 0 · X_m = {1}

RESOLVIDO Define-se f(0,a) = 1 · f(0,b) = 0 · f(1,a) = 1 · f(1,b) = 0.
Por quê funciona: partindo de 0, o único jeito de chegar ao estado marcado 1 é ocorrer um a. Depois, ou o estado permanece (novo a), ou volta a 0 se ocorrer b — e o processo se repete. Logo L_m(G) = L. Como aqui f é total, L(G) = E*: o autômato gera tudo, mas marca só o que termina em a.

Ex. 2.5 Linguagem gerada × marcada

Exemplo 2.5 — Fig. 2.2 sem o self-loop b no estado 0

agora f(0,b) é indefinida → f deixa de ser total

RESOLVIDO Removido o self-loop, L(G) passa a ser: ε junto com as cadeias que começam com a e não têm dois b's consecutivos (todo b é o último evento ou é imediatamente seguido de a).
L_m(G) é o subconjunto dessas cadeias que terminam em a. Agora L(G) ⊂ E*: um autômato representa duas linguagens, e permitir f parcial é o que modela "o sistema não consegue executar tudo".

Ex. 2.6 Autômatos equivalentes em linguagem

G₁ e G₂ são equivalentes em linguagem se L(G₁) = L(G₂) e L_m(G₁) = L_m(G₂).

Fig. 2.3 — três autômatos equivalentes (Exemplo 2.6)

2 estados

3 estados

… e um terceiro, com infinitos estados

os três geram e marcam exatamente as mesmas linguagens do Exemplo 2.5

RESOLVIDO Os três têm estruturas completamente diferentes (2, 3 e infinitos estados) mas geram e marcam as mesmas linguagens. Conclusão: a representação por autômato de uma linguagem não é única — o que importa é o comportamento, não a estrutura interna. (Isso motiva a busca do menor autômato possível — seção 14.)

2. Bloqueio — Deadlock e Livelock

Sempre vale L_m(G) ⊆ L̄_m(G) ⊆ L(G).
G é bloqueante se L̄_m(G) ⊂ L(G) (inclusão estrita): existe cadeia gerada que não pode mais ser completada até um estado marcado.
Deadlock: Γ(x) = ∅ com x ∉ X_m — trava. · Livelock: conjunto fortemente conexo de estados não marcados sem transição de saída — "vivo", mas nunca conclui.

Ex. 2.7 Um autômato bloqueante

Fig. 2.4 — autômato bloqueante do Exemplo 2.7

X_m = {2} · o estado 5 é deadlock · os estados {3, 4} formam um livelock

RESOLVIDO Deadlock: Γ(5) = ∅ e 5 ∉ X_m — ao chegar em 5 nada mais ocorre e a tarefa não foi concluída.
Livelock: {3, 4} formam um componente fortemente conexo absorvente (b: 3→4, a: 4→3, g: self-loop em 4) e nenhum dos dois é marcado — toda cadeia que alcança 3 fica presa aí para sempre.
Conclusão: ag ∈ L(G) mas ag ∉ L̄_m(G) (leva ao deadlock 5); o mesmo vale para qualquer cadeia que comece com aa (leva ao livelock). Logo L̄_m(G) ⊂ L(G) e G é bloqueante.

Ex. 2.8 Deadlock em banco de dados

Exemplo 2.8 — execução concorrente de duas transações

r_i(x) = transação i lê o dado x · w_i(x) = transação i escreve x

RESOLVIDO O autômato H_a deveria marcar exatamente os escalonamentos admissíveis das transações r₁(a)r₁(b) e r₂(a)w₂(a)r₂(b)w₂(b) — com um único estado marcado, alcançado quando ambas as transações terminam.
O escalonamento Sₒ = r₁(a) r₂(a) w₂(a) r₂(b) w₂(b) é admissível, mas sua única continuação possível — o evento r₁(b) — é inadmissível. Logo o estado alcançado após Sₒ é um deadlock e H_a é um autômato bloqueante.

Ex. 2.9 Livelock em telefonia

Exemplo 2.9 — três usuários com "siga-me" em ciclo

usuário 1 encaminha para 2, 2 para 3, e 3 para 1

RESOLVIDO O estado marcado é o próprio estado inicial (todas as chamadas se completam e o sistema volta ao repouso). Com o encaminhamento em ciclo, qualquer pedido de conexão gera uma sequência infinita de eventos de encaminhamento sem que nenhuma ligação se complete — o sistema fica "vivo" mas nunca retorna ao estado marcado: livelock, logo o modelo é bloqueante.
(Na prática o usuário desligaria de frustração — mas esse evento não está no modelo!)

3. Ex. 2.10 — Verificação de Status de Máquina

E = {a₁, a₂, b}. Uma tarefa é uma sequência de 3 eventos ou mais: começa com b, depois a₁ ou a₂ na segunda posição, e b na terceira; o que vem depois é irrelevante. O autômato deve marcar exatamente essas cadeias.

INTERPRETAÇÃO DOS ESTADOS 0 Inicializando · 1 "Estou ligado" · 2 "Meu status está OK" · 3 "Tenho um problema" · 4 "Relatório concluído" ✓ · 5 Erro

⚡ Fig. 2.5 — interativo: tente completar a tarefa (b · a₁/a₂ · b)

RESOLVIDO f é total: todo evento está definido em todo estado — qualquer entrada inesperada é enviada ao estado 5. Isso garante que o dispositivo aceita qualquer entrada, esperada ou não.
O autômato é bloqueante: o estado 5 é um livelock — uma vez nele, o estado marcado 4 é inalcançável.
Observação útil: os estados 2 e 3 podem ser fundidos sem alterar L(G) nem L_m(G) (ambos vão para 4 com b e para 5 com a₁/a₂) — prévia da minimização de estados da seção 14.

4. Ex. 2.11 — Sistema de Fila e Servidor com Falhas

O mesmo sistema físico admite modelos em níveis de abstração diferentes — e a escolha muda radicalmente o tamanho do espaço de estados.

(i) FILA COMPLETA — ESTADO = Nº DE CLIENTES E = {a chegada, d partida} · X = {0, 1, 2, …} (infinito, mas contável)
f(x, a) = x + 1 ∀x ≥ 0 · f(x, d) = x − 1 se x > 0

Fig. 2.6 — modelo da fila (espaço de estados infinito)

X_m fica não especificado neste modelo

(ii) SÓ O SERVIDOR — ABSTRAÇÃO FINITA E = {α início de serviço, β fim, λ quebra, μ conserto} · X = {I, B, D}
Γ(I) = {α} · Γ(B) = {β, λ} · Γ(D) = {μ}

⚡ Fig. 2.7 — interativo: ciclo de vida do servidor

RESOLVIDO Na fila completa, Γ(0) = {a} — não há partida com a fila vazia, então f(0,d) fica indefinida (mais um caso natural de f parcial).
No modelo do servidor, após a quebra o cliente em serviço é perdido; por isso o conserto leva D → I (ocioso) e não de volta a B.
Detalhe conceitual: intuitivamente α deveria ocorrer sempre que se entra em I (não deixar o servidor ocioso à toa), mas isso é impossível quando a fila está vazia — e este modelo não conhece o tamanho da fila. Por isso tratamos α como puramente exógeno: o preço da abstração.

5. Autômatos Não Determinísticos (§2.2.4–2.2.5)

G_nd = (X, E ∪ {ε}, f_nd, Γ, x₀, X_m), com duas diferenças:
① f_nd : X × (E ∪ {ε}) → 2^X — um evento pode levar a um conjunto de estados;
② o estado inicial pode ser um conjunto x₀ ⊆ X.
Motivação: ignorância sobre o efeito exato de um evento, fusão de estados, e ε-transições (mudanças internas não observáveis).

Ex. 2.12 Um autômato não determinístico simples

Fig. 2.8 — Exemplo 2.12

f_nd(0,a) = {0,1} · f_nd(1,b) = {0} · f_nd(0,b) e f_nd(1,a) indefinidas

RESOLVIDO Ao ocorrer a no estado 0, o sistema pode ir para 0 ou 1 — não sabemos qual.
O que marca: qualquer cadeia só de a's (fazendo os self-loops e ficando em 0, que é marcado), e qualquer cadeia contendo ab desde que esse b seja imediatamente seguido de a ou encerre a cadeia.
Note que aa é marcada mesmo podendo também levar ao estado 1 (não marcado): basta existir um caminho que termine em estado marcado.

Ex. 2.13 Não determinismo com ε-transição

Fig. 2.9 — Exemplo 2.13

f_nd(1,b)={2} · f_nd(1,ε)={3} · f_nd(2,a)={2,3} · f_nd(2,b)={3} · f_nd(3,a)={1}

RESOLVIDO Após "ligar" o sistema observamos o evento a — mas f_nd(1,a) não está definida! Conclusão: houve antes a transição silenciosa 1 →^ε 3, e então 3 →^a 1. Logo, logo após o a o sistema está em 1 — embora possa migrar de novo para 3 sem gerar rótulo observável.
Se a cadeia observada é baa, o sistema pode estar em qualquer dos três estados, dependendo de quais a's foram executados: a incerteza vem das ε-transições.

εR(x) = estados alcançáveis de x só por ε-transições (por convenção x ∈ εR(x)); εR(B) = ∪_x∈B εR(x).
f_nd^ext(x, ε) := εR(x) · f_nd^ext(x, ue) := εR[{z : z ∈ f_nd(y,e), y ∈ f_nd^ext(x,u)}]
L(G_nd) = {s : ∃x∈x₀, f^ext(x,s) definida} · L_m(G_nd) = {s ∈ L : ∃x∈x₀, f^ext(x,s) ∩ X_m ≠ ∅}

VALORES RESOLVIDOS Fig. 2.8: f^ext(0,ab) = {0} — pois f_nd(0,a) = {0,1}, f_nd(0,b) é indefinida e f_nd(1,b) = {0}.
Fig. 2.9: f^ext(1,ε) = {1,3} · f^ext(3,a) = {1,3} · f^ext(1,baa) = {1,2,3} · f^ext(1,baabb) = {3}.

Autômatos com entradas e saídas (§2.2.5)

Moore: a saída está associada ao estado (generaliza a marcação — por exemplo, a leitura dos sensores naquele estado físico). Mealy: as transições são rotuladas entrada/saída.

Fig. 2.10 — Moore: válvula + sensor de fluxo

em verde, a saída (leitura do sensor) emitida ao entrar no estado

Fig. 2.11 — conversão Moore → Mealy

Moore: saída no estado

Mealy: saída na transição

A regra: cada transição recebe a saída do estado em que ela entra. Assim, todo o material para autômatos padrão vale também para Moore/Mealy — em Mealy basta ver E como o conjunto dos pares entrada/saída.

6. Operações Unárias — Ac, CoAc, Trim, Comp (§2.3.1)

Ac(G) — apaga estados inacessíveis a partir de x₀. Não altera L nem L_m (por isso assume-se sempre G = Ac(G)).
CoAc(G) — apaga estados que não alcançam X_m. Pode encolher L(G); nunca altera L_m(G). Se G = CoAc(G) então L(G) = L̄_m(G) — não bloqueante.
Trim(G) = CoAc[Ac(G)] = Ac[CoAc(G)] — acessível e coacessível (as operações comutam).
Comp(G) — marca E* \ L_m(G): ① completa f com um estado "lixeira" x_d (tornando f total); ② inverte a marcação de todos os estados.

Ex. 2.14 As quatro operações aplicadas

Fig. 2.12 — autômato G: a Fig. 2.4 com um estado 6 a mais

o estado 6 tem duas transições (6→2 por b e 6→3 por a), mas não é alcançável a partir de 0

Fig. 2.13 — resultados das operações

(a) CoAc(G)

(b) Trim(G)

estado lixeira d recebe todas as transições que faltavam; a marcação é invertida

RESOLVIDO — PASSO A PASSO Ac(G): basta apagar o estado 6 e suas duas transições — volta-se exatamente à Fig. 2.4.
CoAc(G): os estados que não alcançam o marcado 2 são 3, 4 e 5; apagam-se eles. Note que o estado 6 permanece, pois alcança 2 — ser inacessível não importa para CoAc.
Trim(G): aplicando as duas (em qualquer ordem) restam {0, 1, 2}.
Comp[Trim(G)]: em Trim(G) temos Γ(0)={a}, Γ(1)={b}, Γ(2)={g}. Com E = {a,b,g}, completam-se as faltantes até a lixeira d: 0 →^b,g d, 1 →^a,g d, 2 →^a,b d, mais o self-loop a,b,g em d. Depois inverte-se a marcação: como X_m era {2}, agora os marcados são {0, 1, d}.

7. Composição por Produto — G₁ × G₂ (§2.3.2)

Estados são pares (x₁, x₂); o evento e só ocorre se e ∈ Γ₁(x₁) ∩ Γ₂(x₂) — os dois autômatos andam sempre juntos ("lock-step").
L(G₁×G₂) = L(G₁) ∩ L(G₂) · L_m(G₁×G₂) = L_m(G₁) ∩ L_m(G₂)
→ o produto implementa a interseção de linguagens. É comutativo e associativo.

Ex. 2.15 Produto de dois autômatos

Fig. 2.15 (i) — produto das Figs. 2.1 e 2.2

eventos comuns {a, b}; só a chega a ser ativo

Fig. 2.15 (ii) — produto das Figs. 2.2 e 2.13(b)

o único comportamento comum é a cadeia ab

RESOLVIDO (i) No estado inicial (x,0), o único evento comum possível é a, levando a (x,1). Comparando os eventos ativos de x e de 1, de novo só a é comum — e leva x→x e 1→1, isto é, self-loop em (x,1). O autômato está completo com 2 estados. O evento b nunca aparece porque o autômato da Fig. 2.1 nunca alcança um estado em que b seja factível. O estado (x,1) é marcado, pois x e 1 são marcados nos respectivos autômatos.
(ii) Aqui o único comportamento comum é ab: (0,0) →^a (1,1) →^b (0,2), e nesse ponto o produto entra em deadlock. Como X_m1×X_m2 = {(1,2)} não é alcançável, nenhum estado é marcado e L_m = ∅ — coerente com o fato de as linguagens marcadas dos dois fatores não terem cadeia em comum.

8. Composição Paralela — G₁ ‖ G₂ (§2.3.2)

Evento comum (e ∈ E₁ ∩ E₂): só ocorre se ambos puderem executá-lo — e ambos transitam.
Evento privado (e ∈ E₁\E₂ ou E₂\E₁): o dono executa livremente; o outro não se move.
Casos extremos: se E₁ = E₂, reduz-se ao produto; se E₁ ∩ E₂ = ∅, é o shuffle (concorrência total).
Com as projeções P_i : (E₁∪E₂)* → E_i*: L(G₁‖G₂) = P₁⁻¹[L(G₁)] ∩ P₂⁻¹[L(G₂)].

Ex. 2.16 Composição paralela das Figs. 2.1 e 2.2

⚡ Fig. 2.16 — interativo: g move só G₁ · a, b movem os dois

RESOLVIDO G₁ = Fig. 2.1 (E₁ = {a,b,g}), G₂ = Fig. 2.2 (E₂ = {a,b}). Comuns: {a, b}; g é privado de G₁.
No estado inicial (x,0), além do comum a → (x,1), G₁ pode executar g sozinho, levando a (z,0) — G₂ permanece em 0. Repetindo em largura, todos os 6 estados de X₁×X₂ são alcançáveis.
Compare com o produto do Ex. 2.15(i), que tinha apenas 2 estados: a composição paralela preserva o comportamento privado de cada componente e por isso é sempre "mais rica".

Ex. 2.17 Associatividade — e a armadilha do conjunto de eventos

Fig. 2.17 — três autômatos

G₁ · E₁={a,b,c}

G₂ · E₂={a,b,d}

G₃ · E₃={a,b,c}

Resultados da composição

G₁₂ = G₁‖G₂

G₁₂‖G₃

RESOLVIDO Em G₁₂ = G₁‖G₂ temos L(G₁₂) = c̄*₃a₃d̄*, isto é {c}*{a}{d}* : o evento b nunca chega a ocorrer, porque nos dois únicos estados alcançáveis (1,A) e (2,B) ele não é comum-factível.
A armadilha: se ao compor com G₃ você "esquecer" E₁∪E₂ e usar apenas os eventos ativos de G₁₂ (que são a, c, d), concluiria — erradamente — que b é privado de G₃ e poderia ocorrer sozinho.
Correto: b é comum a todos os três e só ocorre se todos puderem executá-lo. Resultado real de G₁‖G₂‖G₃: um único estado (1,A,D) com self-loop c — G₁ só consegue executar c, pois a é impedido por G₃, e b é impedido por G₁.
Lição: por isso o conjunto de eventos de G₁‖G₂ é definido como E₁ ∪ E₂ — e não inferido do diagrama.

9. Ex. 2.18 — Jantar dos Filósofos (2 usuários, 2 recursos)

Dois filósofos numa mesa redonda com dois garfos. Cada um pensa (T) ou come (E); para comer precisa pegar os dois garfos, um de cada vez, em qualquer ordem; ao terminar devolve ambos. Eventos: ifj = "filósofo i pega o garfo j" · if = "filósofo i devolve os dois garfos".

Fig. 2.18 — os dois filósofos

P₁

P₂

… e os dois garfos (controladores de recurso)

F₁ · garfo 1

F₂ · garfo 2

cada garfo alterna entre disponível (A) e em uso (U); seus eventos são comuns aos dos filósofos

Por que os garfos são necessários: P₁ e P₂ sozinhos não têm eventos em comum, então P₁‖P₂ é um shuffle com 16 estados alcançáveis — incluindo situações fisicamente impossíveis, como o mesmo garfo sendo usado pelos dois ao mesmo tempo. Os autômatos F₁ e F₂ introduzem os eventos comuns que impõem a restrição de recurso.

Fig. 2.19 — PF = P₁‖P₂‖F₁‖F₂: apenas 9 dos 64 estados são alcançáveis

os dois estados em vermelho são deadlocks: cada filósofo segura um garfo e espera o outro para sempre

RESOLVIDO Redução do espaço de estados: de 64 possíveis (4×4×2×2) restam 9 alcançáveis — os eventos comuns "podam" drasticamente a composição.
PF é bloqueante: os estados (1I1, 2I2, 1U, 2U) e (1I2, 2I1, 1U, 2U) são deadlocks. Em (1I1,2I2,1U,2U), por exemplo, P₁ tem o garfo 1 e quer o 2 (mas F₂ está em 2U), enquanto P₂ tem o garfo 2 e quer o 1 (mas F₁ está em 1U) — ambos morrem de fome.
Solução (exercício do livro): acrescentar um controlador de prevenção de deadlock C que proíba um filósofo de pegar um garfo livre quando o outro filósofo já segura o outro garfo, de modo que PF ‖ C = CoAc(PF).
Lição de modelagem: a composição paralela é o mecanismo de controle — cada garfo é um controlador do seu próprio recurso. Isso só funciona com ‖ (com × seria preciso acrescentar self-loops em todos os estados).

Maldição da dimensionalidade: 10 componentes de 5 estados com conjuntos de eventos disjuntos → o shuffle tem 5¹⁰ ≈ 10 milhões de estados. Eventos comuns podam esse crescimento (como aqui: 9 de 64), mas o pior caso continua exponencial no nº de componentes — o desafio computacional central em SED.

10. Refinamento do Espaço de Estados e Subautômato (§2.3.3)

O problema: com L₁ ⊆ L₂, queremos mapear cada estado de G₁ no estado correspondente de G₂. Mas duas cadeias t₁ e t₂ que chegam ao mesmo estado de G₁ podem levar a estados diferentes em G₂ — o mapa não seria uma função do estado.

Ex. 2.19 Refinamento por produto

Fig. 2.20 (i) — autômato G₁

o estado x₂ é alcançado tanto por a₁ quanto por a₂

Fig. 2.20 (ii) — autômato G₂

aqui a₁ e a₂ levam a estados diferentes: y₂ e y₃

Fig. 2.20 (iii) — o produto G₁ × G₂ refina G₁

x₂ foi dividido em (x₂,y₂) e (x₂,y₃) — ler a 2ª componente dá o estado de G₂

RESOLVIDO Basta construir G_1,new = G₁ × G₂. Como L(G₁) ⊆ L(G₂), esse produto é equivalente em linguagem a G₁, mas cada estado passa a ser um par (x, y): basta ler a segunda componente para saber em que estado G₂ está.
No exemplo, o estado x₂ correspondia a y₂ (se alcançado por a₁) ou a y₃ (se alcançado por a₂); após o refinamento ele se divide em (x₂,y₂) e (x₂,y₃), e o mapa vira uma função bem definida do estado — independente da cadeia usada para chegar lá.

G₁ ⊑ G₂ se f₁(x₀₁, s) = f₂(x₀₂, s) para toda s ∈ L(G₁) — o diagrama de G₁ é literalmente um subgrafo do de G₂ (implica X₁ ⊆ X₂, x₀₁ = x₀₂ e L(G₁) ⊆ L(G₂); com marcação, X_m,1 = X_m,2 ∩ X₁).
É uma correspondência mais forte que o refinamento por produto: casar os estados fica trivial, mas pode ser preciso modificar os dois autômatos.

11. Autômato Observador — Obs(G_nd) (§2.3.4)

Passo 1: x_0,obs := εR(x₀); X_obs = {x_0,obs}.
Passo 2: para cada B ∈ X_obs e e ∈ E: f_obs(B,e) := εR({x : x ∈ f_nd(x_e,e), x_e ∈ B}), quando não vazio.
Passo 3: repetir até fechar a parte acessível. Passo 4: marcar B se B ∩ X_m ≠ ∅.
Propriedades: é determinístico · L(Obs) = L(G_nd) · L_m(Obs) = L_m(G_nd). Estados ⊆ 2^X, logo finito se X for finito.

Ex. 2.20 Um determinístico equivalente

Fig. 2.21 — o observador do autômato da Fig. 2.8

A corresponde a {0} e B corresponde a {0,1}

RESOLVIDO — VERIFICANDO A CORRESPONDÊNCIA (i) f(A,a) = B ↔ f_nd(0,a) = {0,1}; (ii) f(A,b) e f_nd(0,b) são ambas indefinidas; (iii) f(B,a) = B ↔ f_nd(0,a) = {0,1} com f_nd(1,a) indefinida; (iv) f(B,b) = A ↔ f_nd(1,b) = {0} com f_nd(0,b) indefinida.
Ambos os estados do observador são marcados, pois contêm o estado 0 (marcado em G_nd).

Ex. 2.21 Construção completa do observador

Fig. 2.22 (i) — o autômato não determinístico G_nd

X_m = {0} · note as ε-transições 1→2 e 2→3

Fig. 2.22 (ii) — o observador Obs(G_nd), determinístico

cada estado é um conjunto de estados de G_nd — a estimativa do observador externo

RESOLVIDO — PASSO A PASSO ① Estado inicial: εR(0) = {0} — e já marcado, pois 0 ∈ X_m.
② Em {0} só a está definido: a cadeia a leva G_nd a 1 (via a), 2 (via aε) e 3 (via aεε). Cria-se {0} →^a {1,2,3}.
③ Em {1,2,3}, a união dos eventos ativos é {a, b}. Com a: só o estado 2 tem a, levando a 0 — logo {1,2,3} →^a {0}.
④ Com b: de 1 alcança-se 1 (via b), 2 (via bε) e 3 (via bεε); de 3 alcança-se 0. União: {1,2,3} →^b {0,1,2,3} — marcado, pois contém 0.
⑤ Em {0,1,2,3}: com a, de 0 chega-se a 1,2,3 e de 2 chega-se a 0 → todo o conjunto (self-loop). Com b, raciocínio análogo → outro self-loop.
Fim: todos os estados criados foram examinados. Obs(G_nd) tem 3 estados e é equivalente em linguagem a G_nd.

12. Equivalência de Autômatos — Bissimulação (§2.3.5)

Fig. 2.23 — mesma linguagem, comportamentos diferentes

H · determinístico

G · não determinístico

em G, após a o sistema pode executar ou b, ou c — nunca ambos

RESOLVIDO H e G são equivalentes em linguagem (geram e marcam o mesmo). Mas em G, dependendo de qual ramo a tomou, só b ou só c fica disponível; em H, após a, ambos continuam possíveis. O modelador usou o não determinismo de propósito — para capturar uma escolha interna não modelada (ou o efeito do ambiente). Logo, "equivalente em linguagem" é fraco demais aqui.

B1: todo estado de um lado tem par no outro (nas duas direções).
B2: se (x_H, x_G) ∈ Φ e um deles transita com e ∈ E_R, o outro também transita com e, e os destinos continuam relacionados por Φ (nas duas direções).
B3 (opcional): estados relacionados concordam na marcação.
Resultado na Fig. 2.23: com E_R = E, os pares (B,2) e (B,2') não podem estar em Φ — B e 2 divergem em c, B e 2' divergem em b — logo H e G não são bissimilares. Já restringindo a E_R = {a}, são bissimilares, com Φ contendo (A,1), (B,2), (B,2'), (C,3), (D,4).

Simulação: relaxando B1(b) e B2(b), exige-se apenas que toda transição de G exista em H — diz-se que H simula G. Útil para abstrações: o modelo abstrato reproduz todos os comportamentos, podendo incluir alguns a mais. Se H simula G e G simula H, são bissimilares. Autômatos bissimilares não precisam ser isomorfos, e a bissimilaridade é uma relação de equivalência.

13. Linguagens Regulares e Expressões Regulares (§2.4.1–2.4.2)

Toda linguagem pode ser marcada por um autômato — basta construir a árvore cujos nós no nível n são os prefixos de comprimento n. O problema é que essa árvore é infinita sempre que a linguagem for infinita.

Fig. 2.24 — autômato-árvore para L = {aⁿbⁿ : n ≥ 0}

cada nível exige novos estados: nenhuma quantidade finita de memória basta

L é regular se pode ser marcada por um autômato de estados finitos. R é um subconjunto próprio de 2^E*.
Por que aⁿbⁿ não é regular: o estado marcado só pode ser alcançado após exatamente o mesmo número de b's e de a's, logo o autômato precisa "memorizar" quantos a's ocorreram — para marcar aᴢbᴢ sem marcar cadeias fora de L são necessários ao menos 2N−1 estados, e N é ilimitado.
Teorema: autômatos finitos não determinísticos e determinísticos representam exatamente a mesma classe R (o observador de um NFA finito é finito).
R é fechada sob: complemento L̄, fecho de Kleene L*, complementar E*\L, união, concatenação e interseção (esta última via produto).

Ex. 2.22 Expressões regulares

Autômatos que marcam as expressões do Exemplo 2.22

E = {a, b, g}

RESOLVIDO (a + b)g* denota L = {a, b, ag, bg, agg, bgg, aggg, bggg, …} — cadeias que começam com a ou b e seguem com qualquer repetição de g. Mesmo sendo L infinita, a expressão é uma representação finita.
(ab)* + g denota L = {ε, g, ab, abab, ababab, …} — a cadeia vazia, o evento g, ou qualquer repetição de ab.
Teorema de Kleene: toda linguagem denotada por expressão regular é regular, e toda linguagem regular pode ser denotada por uma expressão regular — expressões regulares ⇔ autômatos finitos.

14. Ex. 2.23 — Minimização de Estados (§2.4.3)

Supondo f totalmente definida (L(G) = E*): x e y são equivalentes se L_m(G(x)) = L_m(G(y)) — mesmo comportamento futuro. Estados equivalentes podem ser fundidos.
O menor autômato que marca L é o reconhecedor canônico, único a menos de renomear estados; ‖L‖ é seu nº de estados. Atenção: ‖L‖ nada tem a ver com a cardinalidade de L — por exemplo ‖E*‖ = 1, embora E* seja infinita.

O problema: E = {1, 2, 3}; marcar toda cadeia que termina com a subcadeia 123, aceitando qualquer dígito a qualquer momento (f total, L(G) = E*).

CONSTRUÇÃO — "MEMORIZAR O SUFIXO RELEVANTE" A lógica: o autômato só precisa lembrar qual sufixo útil foi lido até agora — 1, 12, 123, ou nenhum deles. Daí os estados x₀ (nada lido), x₁ (sufixo "1"), x₁₂ (sufixo "12"), x₁₂₃ (sufixo "123", marcado) e x_not1 (nenhum dos anteriores).

Fig. 2.25 (i) — o modelo direto, com 5 estados

em azul, as transições que "quebram" o sufixo e caem em x_not1

estado \ evento	1	2	3
x₀	x₁	x_not1	x_not1
x₁	x₁	x₁₂	x_not1
x₁₂	x₁	x_not1	x₁₂₃ ✓
x₁₂₃	x₁	x_not1	x_not1
x_not1	x₁	x_not1	x_not1

MINIMIZAÇÃO — DE 5 PARA 4 ESTADOS Compare as linhas de x₀ e x_not1: as transições são idênticas para todo evento (1→x₁, 2→x_not1, 3→x_not1) e nenhum dos dois é marcado → são equivalentes e podem ser fundidos em x_0,new. Verifica-se que no autômato de 4 estados não restam equivalentes: ele é o reconhecedor canônico, com ‖L‖ = 4.

⚡ Fig. 2.25 (ii) — interativo: o detector minimizado (4 estados)

Passo 1: marcar ("flag") todo par (x,y) com x ∈ X_m e y ∉ X_m — nunca podem ser equivalentes.
Passo 2: para cada par ainda sem flag: se (f(x,e), f(y,e)) já tem flag para algum e, marcar (x,y) e propagar o flag a todos os pares da sua lista; senão, registrar (x,y) na lista de (f(x,e), f(y,e)) para o caso de esse par ser marcado depois.
Ao final, os pares sem flag são os equivalentes; agrupam-se por transitividade e cada grupo vira um estado agregado.

RESOLVIDO — APLICANDO À TABELA DA FIG. 2.26 • Marcam-se todos os pares da 1ª coluna (envolvendo o marcado x₁₂₃).
• (x₁₂, x₀): f(x₁₂,3) = x₁₂₃ e f(x₀,3) = x_not1, e (x₁₂₃, x_not1) já tem flag → marcar.
• (x₁₂, x₁) e (x₁₂, x_not1): mesmo argumento com o evento 3 → marcar.
• (x_not1, x₁): f(x_not1,2) = x_not1, f(x₁,2) = x₁₂, e (x₁₂, x_not1) já tem flag → marcar.
• (x₁, x₀): f(x₁,2) = x₁₂, f(x₀,2) = x_not1, par já marcado → marcar.
• (x_not1, x₀): nunca recebe flag, pois f(x_not1,e) = f(x₀,e) para todo e ∈ {1,2,3}. ✓
É exatamente o par equivalente encontrado por inspeção — e o único.

15. Análise de SED — Segurança, Bloqueio e Observação Parcial (§2.5)

Tratam da alcançabilidade de estados indesejáveis, da presença de cadeias proibidas, ou da inclusão de L(G) numa linguagem "legal". Algoritmos (todos polinomiais):
• y é alcançável a partir de x? → aplicar Ac(·) com x como inicial e procurar y. O(n).
• a subcadeia w é possível? → tentar "executar" w a partir de cada estado acessível.
• A ⊆ B? → equivale a A ∩ Bᶜ = ∅: construir o complemento de B e tomar o produto com A. O(n₁n₂).
Lembrando o custo das composições: as unárias são O(n) (uma varredura do diagrama); produto e paralela são O(n₁n₂).

Pergunta central: L̄_m(G) = L(G) ou ⊂? → aplicar CoAc(·): se algum estado for deletado, G é bloqueante; caso contrário é não bloqueante.
Deadlocks: estados não coacessíveis com Γ(x) = ∅. · Livelocks: componentes fortemente conexos da parte não coacessível (algoritmos de SCC em O(n)).

Particiona-se E = E_o ∪ E_uo (observáveis / não observáveis) — sensor ausente, evento remoto não comunicado, ou falha silenciosa. O modelo continua determinístico; basta tratar os eventos de E_uo como ε e construir o observador sobre E_o.
Generalizando o ε-alcance, define-se o alcance não observável:
UR(x) = {y ∈ X : ∃t ∈ E_uo*, f(x,t) = y} · UR(B) = ∪_x∈B UR(x)
(O observador com UR e a diagnose de eventos — §2.5.2–2.5.3 — ficam para a próxima ficha.)