§2.2.1 Modelos de Linguagem de Sistemas a Eventos Discretos
Como o framework "alfabeto + palavras" captura o comportamento lógico de um SED
Baseado em: Cassandras & Lafortune, "Introduction to Discrete Event Systems", 2ª Ed. — Seção 2.2.1
1. A Ideia Central
Ideia-chave: Todo SED possui um conjunto de eventos E associado a ele. Se tratarmos E como um alfabeto e as sequências de eventos como palavras, podemos estudar o comportamento lógico do sistema usando a teoria formal de linguagens. As perguntas centrais passam a ser: "Podemos construir um sistema que fale uma dada linguagem?" e "Qual linguagem esse sistema fala?"
2. Exemplo Motivador — Verificação de Status da Máquina
Imagine uma máquina que você liga uma ou duas vezes por dia — um carro, uma copiadora ou um computador de mesa. Queremos projetar um sistema simples que realize a seguinte tarefa: quando a máquina é ligada, ela deve (1) sinalizar que está LIGADA, (2) fornecer um relatório de status e (3) sinalizar que o relatório foi concluído.
⚡ Interativo — selecione um cenário abaixo
🖥️
Máquina
DESLIGADA
1
"Estou LIGADA"
evento: on
→
2
relatório de statusevento: ?
→
3
"Relatório pronto"
evento: done
3. O Alfabeto (Conjunto de Eventos E)
Cada sinal que a máquina pode emitir define um evento. O conjunto de todos os sinais possíveis é o alfabeto da linguagem do nosso SED.
Uma palavra (ou cadeia/string) é uma sequência de eventos do alfabeto. A linguagem de interesse aqui consiste em palavras de exatamente três eventos, sempre começando com on e terminando com done, com um evento de status no meio.
PALAVRA (CADEIA)
EVENTOS
STATUS
INTERPRETAÇÃO
on · ok · done
3
✓ VÁLIDA
Normal — tudo funcionando
on · oil · done
3
✓ VÁLIDA
Precisa de manutenção
on · gas · done
3
✓ VÁLIDA
Precisa de combustível
on · done
2
✗ INVÁLIDA
Anormal — relatório de status ausente!
ok · on · done
3
✗ INVÁLIDA
Ordem errada — não começa com on
A LINGUAGEM DAS VERIFICAÇÕES DE STATUS VÁLIDASL = { on · s · done : s ∈ {ok, oil, gas} }
L = { on·ok·done, on·oil·done, on·gas·done }
· |L| = 3 palavras
Nota: O SED que construímos é responsável por reconhecer eventos e dar a interpretação correta a qualquer sequência recebida. Uma palavra válida significa que a tarefa foi concluída com sucesso; qualquer outra coisa indica que algo deu errado.
5. Conexão com os Conceitos Formais
Alfabeto (E)
O conjunto finito de todos os eventos. No exemplo: {on, ok, oil, gas, done}. Todo SED começa aqui.
Cadeia / Palavra
Uma sequência finita de eventos de E. on·ok·done é uma cadeia de comprimento 3.
Linguagem (L)
Um conjunto de cadeias sobre E, ou seja, L ⊆ E*. As sequências válidas de verificação de status formam a linguagem L.
Cadeia Vazia (ε)
A cadeia sem nenhum evento. |ε| = 0. É o elemento identidade da concatenação: s·ε = ε·s = s.
Fecho de Kleene (E*)
O conjunto de todas as cadeias de comprimento finito sobre E, incluindo ε. É contavelmente infinito. Toda linguagem é um subconjunto de E*.
Comprimento da Cadeia |s|
O número de eventos na cadeia, contando repetições. |on·ok·done| = 3, |ε| = 0.
6. Por que isso Importa
O framework: Ao modelar um SED como uma linguagem sobre um conjunto de eventos, podemos perguntar rigorosamente: o sistema produz apenas palavras válidas? Ele pode alcançar um estado inseguro? É possível controlá-lo para que apenas sequências legais ocorram? Esses são exatamente os problemas de verificação e controle que conduzem o restante do Capítulo 2.
🔍 Verificação
A linguagem L do sistema contém apenas palavras seguras? Existem prefixos inseguros que poderiam se infiltrar?
⚙️ Controle
Podemos restringir o sistema para que a linguagem gerada permaneça dentro de uma especificação desejada?
🤖 Autômatos
A forma prática de implementar um reconhecedor de linguagem — máquinas de estados finitos que leem palavras e as aceitam ou rejeitam.