Fundamentos: Provas, Alfabetos, Strings e Linguagens
Técnicas de prova e os conceitos centrais da teoria de autômatos
Baseado em: Hopcroft, Motwani & Ullman, "Introdução à Teoria de Autômatos, Linguagens e Computação" — Cap. 1
1. Técnicas de Prova
Grande parte da teoria de autômatos envolve provar propriedades sobre linguagens, autômatos e gramáticas. O livro apresenta seis técnicas fundamentais:
Dedutiva (Se-Então)
Forma: "Se H, então C". Assume H verdadeiro, deriva C por passos lógicos. A mais comum.
Se-e-Somente-Se
Forma: "H ⟺ C". Prova nos dois sentidos: (H→C) e (C→H). Equivale a provar igualdade de conjuntos.
Contrapositiva
Em vez de "Se H então C", prova "Se ¬C então ¬H". Logicamente equivalente, às vezes mais fácil.
Contradição
Assume H e ¬C, deduz algo absurdo. Logo ¬C é impossível, e C deve ser verdadeiro.
Contra-exemplo
Para refutar "∀x, P(x)", basta achar UM x onde P(x) é falso. Ex: "Todo primo é ímpar" → 2 é primo e par. ✗
Indução
Prova S(n) para todo n: mostra BASE (n=0) e PASSO INDUTIVO (S(n)→S(n+1)). Também existe indução estrutural.
Exemplo Interativo — Prova por Indução
Teorema 1.16: Para todo n ≥ 0, a soma 1 + 2 + ... + n = n(n+1)/2.
Clique em cada passo para revelar a prova
BASE Para n = 0: lado esquerdo = 0 (soma vazia). Lado direito = 0·1/2 = 0. ✓
HIPÓTESEClique para revelar...
INDUÇÃOClique para revelar...
CONCLUSÃOClique para revelar...
Teorema 1.5 — Prova por Contradição
Teorema: Se S é um conjunto finito e T é infinito, então T − S é infinito.
Clique em cada passo para revelar a prova
HIPÓTESE Suponha por contradição que T − S é finito.
RACIOCÍNIOClique para revelar...
CONTRADIÇÃOClique para revelar...
Supostos Teoremas 1.13 e 1.14 — Contra-exemplos
Refutando afirmações falsas com um único contra-exemplo
1.13 "Todo primo é ímpar" → Contra-exemplo: 2. O número 2 é primo e par. ✗ Refutado.
1.14 "Não existem a,b tais que a mod b = b mod a" → Contra-exemplo: a=b=1. 1 mod 1 = 0 = 1 mod 1. ✗ Refutado.
Teorema 1.17 — Indução: Série Geométrica
Teorema: Para todo n ≥ 0 e a ≠ 1: 1 + a + a² + ... + aⁿ = (aⁿ⁺¹ − 1)/(a − 1)
Contexto: Autômato com 2 estados (desligado/ligado) e ação "pressionar". Provar simultaneamente: S₁(n) = "desligado após n pressões ⟺ n par" e S₂(n) = "ligado ⟺ n ímpar".
Clique nos passos da indução mútua
BASE n=0: 0 pressões → desligado (inicial). 0 é par → S₁ ✓. S₂ vacuamente verdadeiro ✓.
INDUÇÃOClique para revelar...
CONCLUSÃOClique para revelar...
2. Alfabetos (§1.5.1)
Um alfabeto é um conjunto finito e não-vazio de símbolos. Denotado por Σ.
EXEMPLOS COMUNSΣ = {0, 1} → alfabeto binário Σ = {a, b, ..., z} → letras minúsculas Σ = {conjunto de caracteres ASCII} → usado em compiladores
3. Strings (§1.5.2)
Um string (ou cadeia, palavra) é uma sequência finita de símbolos de algum alfabeto Σ.
String vazio (ε)
O string com zero símbolos. |ε| = 0. Pertence a Σ* para qualquer Σ. É a identidade da concatenação: εw = wε = w.
Comprimento |w|
Número de posições no string. |01101| = 5. |ε| = 0. Note: 01101 tem 2 símbolos distintos mas 5 posições.
Concatenação (xy)
Colar y ao final de x. Se x = 011, y = 10, então xy = 01110 e yx = 10011. Ordem importa!
⚡ Interativo — Construtor de Concatenação
STRING x
vazio
·
STRING y
vazio
=
RESULTADO xy
ε
|x| = 0 · |y| = 0 · |xy| = 0 · xy = ε
Potências do Alfabeto (Σk)
Σk = conjunto de todos os strings de comprimento exatamente k sobre Σ.
Σ⁰
ε
Σ¹
01
Σ²
00011011
Σ³
000001010011100101110111
FECHO DE KLEENE E FECHO POSITIVOΣ* = Σ⁰ ∪ Σ¹ ∪ Σ² ∪ · · · = todos os strings finitos sobre Σ (inclui ε) Σ⁺ = Σ¹ ∪ Σ² ∪ Σ³ ∪ · · · = todos os strings não-vazios (exclui ε) Σ* = Σ⁺ ∪ {ε}
4. Linguagens (§1.5.3)
Uma linguagem sobre Σ é qualquer conjunto L ⊆ Σ*. Pode ser finita, infinita, ou até vazia.
EXEMPLOS DO LIVRO (Σ = {0, 1})
1. L = {ε, 01, 0011, 000111, ...} = { 0n1n : n ≥ 0 } → infinita
2. L = { w ∈ {0,1}* : #0(w) = #1(w) } → infinita
3. L = { representações binárias de primos } = {10,11,101,111,1011,...} → infinita
4. Σ* é uma linguagem sobre Σ → infinita
5. ∅ é uma linguagem sobre qualquer Σ → vazia
6. {ε} é uma linguagem → finita (1 elemento) · note: ∅ ≠ {ε}
Cuidado: ∅ e {ε} são linguagens diferentes! ∅ não tem nenhum string. {ε} tem exatamente um string (o vazio). É como a diferença entre uma caixa vazia e uma caixa com um papel em branco dentro.
Exemplo Interativo — Testador de Pertinência
L = { w ∈ {0,1}* : w contém número igual de 0's e 1's }
L = { w ∈ {0,1}* : w é a representação binária de um primo }
5. Problemas (§1.5.4)
Na teoria de autômatos, um problema é a questão de decidir se um dado string w pertence ou não a uma linguagem L:
Dado w ∈ Σ*, decidir: w ∈ L ?
Isso significa que todo problema de decisão pode ser formulado como pertinência a uma linguagem. Testar se um número é primo? É verificar se sua representação binária pertence a Lprimos. Verificar se um programa C é válido? É verificar se o string ASCII do código pertence a LC. Essa equivalência é a base de toda a teoria de computabilidade.
Problema = Linguagem
Se L descreve os strings "sim", então decidir o problema é construir um autômato (ou algoritmo) que aceite exatamente L.
Linguagem Regular
Se L é aceita por algum DFA, L é regular. Problemas regulares são os "mais fáceis" — decididos com memória finita.