1.1 Representando informações com cadeias
Os modelos da Teoria da Computação são definidos com base em cadeias (ou strings ou pala-
vras), que são sequências de símbolos. Os símbolos vêm de um conjunto finito não-vazio cha-
mado de alfabeto.
• Exemplos de cadeias sobre o alfabeto {a, b}: “a”, “bbaa”, “b”, “abaaa”, etc.
• Exemplos de cadeias sobre o alfabeto {0, 1}: “11”, “0”, “011”, “01001”, etc.
Vamos justificando a seguinte informação: toda informação (processável por humanos) pode
ser representada com cadeias.
Em primeiro lugar, isto faz sentido, porque nós, humanos, representamos as informações com
símbolos. Nem sempre, colocamos os símbolos em sequência – às vezes colocamos em um pa-
pel (2D). Mas sempre é possível transformar outros formatos em sequência.
Em segundo lugar, mostramos abaixo exemplos de vários tipos de informações que podem ser
representadas como cadeias. (Vários estão incompletos, mas tente completar).
- Números naturais representados como cadeias
- o No alfabeto {0, 1, ..., 9}: toda cadeia é uma representação decimal com a qual já
- estamos acostumados (ex.: 12, 42, 539).
- o No alfabeto {0, 1}: usar representação binária.
- o No alfabeto {a}: representar n como n repetições de a (ex.: 3 = aaa).
- Números inteiros como cadeias
o No alfabeto {0, 1, ..., 9, -}: representação que usamos (ex.: -12, 0, 73).
o No alfabeto {0, 1}: começar com 1 se e somente se for negativo.
- • Números com casas decimais finitas como cadeias
o No alfabeto {0, 1, ..., 9, .}: representação que usamos (ex.: 3.14, 8.91).
- • Pares de números naturais (n,m) como cadeias
o No alfabeto {a, b}: n repetições de a seguidas de m repetições de b.
- • Sequências de números naturais como cadeias
o No alfabeto {0, 1, |} : representação binária, e usar | como separador.
- • Imagens preto-e-branco de dimensão (fixa) 4x4 como cadeias
o No alfabeto {0, 1}: 0 para preto, 1 para branco, cadeias de tamanho 16...
- • Imagens preto-e-branco (de quaisquer dimensões) como cadeias
o No alfabeto {p, b, |}: usar | como separador de linhas, etc.
o No alfabeto {0, 1}...
- • Ideias para conversão de qualquer alfabeto, para o alfabeto binário...