Definição de Linguagem · Prefixo, Sufixo e Subcadeia
Notação formal, exemplos expandidos e decomposição visual de cadeias
Baseado em: Cassandras & Lafortune, "Introduction to Discrete Event Systems", 2ª Ed. — Seção 2.2.1
1. Definição Formal de Linguagem
Uma linguagem definida sobre um conjunto de eventos E é um conjunto de cadeias (strings) de comprimento finito formadas a partir de eventos de E.
2. Exemplo do Livro — Expandido
EXEMPLO DO LIVRO
Seja E = {a, b, g} o conjunto de eventos. A partir desse alfabeto de 3 símbolos, podemos definir linguagens muito diferentes:
Linguagem L₁ — Finita e explícita
L₁ = {ε, a, abb} · 3 cadeias FINITAε → cadeia vazia (comprimento 0) a → cadeia de comprimento 1 abb → cadeia de comprimento 3 (concatenação de a, b, b)
Linguagem L₂ — Todas as cadeias de comprimento 3 que começam com a
Se a primeira posição é fixa em a, restam 2 posições livres, cada uma com 3 opções (a, b, g). Isso dá 1 × 3 × 3 = 9 cadeias:
Linguagem L₃ — Todas as cadeias de comprimento finito que começam com a
Agora não há limite de comprimento — apenas a restrição de que a cadeia deve começar com a. Vejamos como ela cresce rapidamente:
L₃ — CADEIAS ORGANIZADAS POR COMPRIMENTO (role para a direita →)
a
aa
ab
ag
aaa
aab
aag
aba
abb
abg
aga
agb
agg
aaaa
aaab
aaag
aaba
aabb
aabg
aaga
aagb
aagg
abaa
abab
abag
abba
abbb
abbg
agaa
agab
agag
· · · ∞
COMPRIMENTO n
QUANTIDADE DE CADEIAS
CADEIAS
1
1 (= 3⁰)
a
2
3 (= 3¹)
aa, ab, ag
3
9 (= 3²)
aaa, aab, aag, aba, abb, abg, aga, agb, agg
4
27 (= 3³)
aaaa, aaab, aaag, aaba, ... (27 cadeias)
n
3n−1
cresce exponencialmente → infinitas cadeias no total
L₃ · |L₃| = ∞ INFINITAL₃ = { s ∈ E* : s começa com a } → total = Σ 3n−1 para n = 1, 2, 3, ... = ∞
3. Prefixo, Subcadeia e Sufixo
Se tuv = s com t, u, v ∈ E*, então:
• t é chamado de prefixo de s
• u é chamado de subcadeia (substring) de s
• v é chamado de sufixo de s
Observação: tanto ε quanto a própria s são prefixos, subcadeias e sufixos de s.
A ideia é simples: toda cadeia s pode ser "fatiada" em três partes consecutivas t · u · v. A parte da esquerda é o prefixo, a do meio é a subcadeia, e a da direita é o sufixo. Qualquer dessas partes pode ser a cadeia vazia ε.
⚡ Interativo — Decomposição da cadeia s = a b b g a
a
b
b
g
a
t = prefixo
u = subcadeia
v = sufixo
4. Exemplo Adicional 1 — Sistema de Alarme Residencial
EXEMPLO NOVO
Considere um sistema de alarme residencial simples. Os eventos possíveis são: armar o alarme, um sensor detectar movimento, a sirene disparar, e o usuário inserir a senha para desarmar. Queremos modelar as sequências válidas de operação.
O alarme é armado, um sensor detecta algo, a sirene toca, e o dono insere a senha. Lok = { arm · sensor · sirene · senha }
|Lok| = 1 cadeia de comprimento 4.
Lfalha — Falso Alarme FINITA
A sirene toca sem detecção prévia de sensor — sequência inválida. Exemplo: arm · sirene · senha
Não pertence a Lok pois pula o evento sensor.
⚡ Interativo — Decomposição da cadeia s = arm · sensor · sirene · senha
arm
sensor
sirene
senha
t = prefixo
u = subcadeia
v = sufixo
5. Exemplo Adicional 2 — Protocolo de Login
EXEMPLO NOVO
Imagine um protocolo de autenticação web. Os eventos são: req (requisição de login), usr (envio do usuário), pwd (envio da senha), ok (acesso concedido) e fail (acesso negado). Existem linguagens de comportamento correto e de tentativas de ataque.