Notas de Aula Teoria da Computa o Ago 2014

CENTRO UNIVERSITÁRIO CARIOCA

UNICARIOCA
TEORIA
DA
COMPUTAÇÃO
NOTAS DE AULA

PROFESSOR: JÚLIO SILVEIRA

VERSÃO: agosto de 2014

TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA
NOTAS DE AULA
I FUNDAMENTAÇÃO TEÓRICA
I.1 DEFINIÇÕES
Símbolo: menor unidade de informação a ser manipulada.
Ex.: a, b, c, 0, 1, S, A, B, …
OBS: Inicialmente, não consideraremos o caracter espaço em branco ' ' como símbolo válido.
Alfabeto: conjunto finito e não vazio de símbolos.
Ex:
Sequência:

A = { a, b }

B = { a, b, c, …, z }

C = { 0, 1 }

(ou cadeia ou palavra)

Concatenação de uma quantidade finita de símbolos de um dado alfabeto.
Ex: sequências com símbolos do alfabeto A acima: a, ab, aaab, bbb, ababa, …
Comprimento de uma sequência: notaçao | |
Número natural que indica a quantidade de (ou ocorrências de) símbolos existentes na sequência.
NOTAÇÃO: o comprimento de uma sequência qualquer , é denotado por | |
Ex:  = a

 ||=1

 = aaba  |  | = 4

ou também

| aaba | = 4

Sequência vazia: 
A sequência vazia, representada por , não contém nenhum símbolo
Desta forma,  tem comprimento ZERO, ou seja: |  | = 0
ATENÇÃO:  não é símbolo! Ou seja, não existe o símbolo . Esta letra grega (leia–se lâmbda) é reservada apenas para caracterizar a seqüência vazia!
Conjuntos de sequências:
Podemos conjuntos cujos elementos são sequências de algum alfabeto.
Ex: X = { a, ab, bbba }

Y={}

Z={ }

W = { , bbbb }
K = { a, ab, abb, abbb, abbbb, abbbbb,  }

ATENÇÃO: as sequências pertencentes a um conjunto não precisam ter todas o mesmo comprimento.

1

TEORIA DA COMPUTAÇÃO – PROF. JÚLIO SILVEIRA
NOTAS DE AULA

2

Cardinalidade de um conjunto de sequências: notaçao | |
Um conjunto de sequências pode ter qualquer nº de elementos. Para os conjuntos anteriores, temos:
Ex.: | X | = 3

|Y| = 1

|Z| = 0

|W| = 2

|K| = 

ATENÇÃO: Observar o contexto na utilização da notação | |
CARDINALIDADE DE UM CONJUNTO:

nº de elementos



|X| = 3

COMPRIMENTO DE UMA SEQÜÊNCIA:

nº de símbolos



| bbba | = 4