Concatenação, fecho de prefixo, fecho de Kleene e pós-linguagem
Baseado em: Cassandras & Lafortune, "Introduction to Discrete Event Systems", 2ª Ed. — Seção 2.2.1, Exemplo 2.1
1. As Quatro Operações
Como linguagens são conjuntos, as operações usuais (união, interseção, diferença, complemento em relação a E*) se aplicam naturalmente. Além delas, existem quatro operações específicas:
Sejam La, Lb ⊆ E*. Então: LaLb := { s ∈ E* : s = sasb , com sa ∈ La e sb ∈ Lb }
Uma cadeia pertence a LaLb se pode ser escrita como a concatenação de uma cadeia de La seguida de uma cadeia de Lb.
Seja L ⊆ E*. Então: L̄ := { s ∈ E* : (∃t ∈ E*) [ st ∈ L ] }
O fecho de prefixo de L é o conjunto de todos os prefixos de todas as cadeias de L.
L é dita prefixo-fechada se L̄ = L (todo prefixo de toda cadeia em L também pertence a L).
Seja L ⊆ E*. Então: L* := {ε} ∪ L ∪ LL ∪ LLL ∪ · · ·
Concatenação de 0, 1, 2, 3, ... elementos de L. Inclui ε (0 concatenações).
A operação é idempotente: (L*)* = L*.
Sejam L ⊆ E* e s ∈ L̄. Então: L/s := { t ∈ E* : st ∈ L }
A pós-linguagem de L após s é o conjunto de sufixos que, concatenados com s, formam cadeias de L.
Se s ∉ L̄, então L/s = ∅.
2. Exemplo 2.1 do Livro
EXEMPLO DO LIVRO
Seja E = {a, b, g}. Considere duas linguagens:
LINGUAGENS DE PARTIDAL₁ = { ε, a, abb } ·
L₄ = { g }
⚡ Interativo — Selecione uma operação
3. Exemplo Adicional — Protocolo Simples
EXEMPLO NOVO
Seja E = {p, q, r}, representando eventos de um protocolo de comunicação: p = pedido, q = confirmação, r = rejeição. Definimos:
LINGUAGENS DE PARTIDALa = { p, pq } ·
Lb = { r, qr }
⚡ Interativo — Selecione uma operação
4. Observações Técnicas
FATOS IMPORTANTES
(i) ε ∉ ∅ ·
(ii) {ε} é uma linguagem não-vazia contendo apenas a cadeia vazia
(iii) Se L = ∅ então L̄ = ∅ · Se L ≠ ∅ então necessariamente ε ∈ L̄
(iv) ∅* = {ε} · {ε}* = {ε}
(v) ∅L = L∅ = ∅
PRECEDÊNCIA
Fecho de prefixo e Kleene primeiro → depois concatenação → depois união, interseção, diferença.