Conjuntos Enumeráveis e Linguagens

Leonardo Reis

Departamento de Ciência da Computação

Universidade Federal de Juiz de Fora

Leonardo Reis DCC055

Introdução

Como fazemos para contar o número de elementos de um conjuntos finito?

▶ Ex.: quantidade de alunos na sala

Apontamos para cada elementos, uma única vez e falamos um número inteiro;
▶ Definimos uma função bijetora f : {1, . . . , n} → A;
▶ Ao apontar para um elemento x e dizer a “posição” y , definimos f (x ) = y ;
▶ Tamanho do conjunto é n.

Leonardo Reis DCC055

Introdução

Como fazemos para contar o número de elementos de um conjuntos finito?

▶ Ex.: quantidade de alunos na sala

Apontamos para cada elementos, uma única vez e falamos um número inteiro;
▶ Definimos uma função bijetora f : {1, . . . , n} → A;
▶ Ao apontar para um elemento x e dizer a “posição” y , definimos f (x ) = y ;
▶ Tamanho do conjunto é n.

Leonardo Reis DCC055

Introdução

Como fazemos para contar o número de elementos de um conjuntos finito?

▶ Ex.: quantidade de alunos na sala

Apontamos para cada elementos, uma única vez e falamos um número inteiro;
▶ Definimos uma função bijetora f : {1, . . . , n} → A;
▶ Ao apontar para um elemento x e dizer a “posição” y , definimos f (x ) = y ;
▶ Tamanho do conjunto é n.

Leonardo Reis DCC055

Cardinalidade

Definição
Suponha que A e B são conjuntos. Dizemos que A e B têm a mesma cardinalidade se existe uma
função bijetora f : A → B. Escrevemos A ∼ B, ou card (A) = card (B ), para dizer que A e B têm a
mesma cardinalidade.

f
Se f é injetora, então |A| ≤ |B |;
Se f é sobrejetora, então |A| ≥ |B |;

Leonardo Reis DCC055

Cardinalidade

Definição
Suponha que A e B são conjuntos. Dizemos que A e B têm a mesma cardinalidade se existe uma
função bijetora f : A → B. Escrevemos A ∼ B, ou card (A) = card (B ), para dizer que A e B têm a
mesma cardinalidade.

f
Se f é injetora, então |A| ≤ |B |;
Se f é sobrejetora, então |A| ≥ |B |;

Leonardo Reis DCC055

Conjuntos Finitos
Conjunto In
Para todo número natural n, definimos In = {i ∈ N∗ | i ≤ n}. Exemplos:
I0 = {};
I5 = {1, 2, 3, 4, 5};
I3 = {1, 2, 3};
I9 = {1, 2, 3, 4, 5, 6, 7, 8, 9};

Definição de Conjuntos Finitos

Um conjunto A é finito se existe um número natural n tal que In ∼ A. Caso contrário, A é infinito.
Se In ∼ A, então o n é único. Logo podemos escrever que |A| = n;
Pela definição segue que I0 ∼ 0/ , logo |0|
/ = 0.

Leonardo Reis DCC055

Conjuntos Infinitos
A definição de cardinalidade pode ser aplicada à conjuntos infinitos?

Leonardo Reis DCC055

Cardinalidade de Z+ e Z
1 Os conjuntos Z+ e Z têm a mesma cardinalidade?
2 Seja a função f : Z+ → Z definida como:
n
se n for par
(
2
f (n) =
1−n
2
se n for ímpar

Prove que f é uma função bijetora.

Relembrando Funções Bijetoras

Como mostrar que uma função f : A → B é bijetora?
1 provar que é injetora: se f (a1 ) = f (a2 ), então a1 = a2 ; e
2 provar que é sobrejetora: ∀m ∈ B ∃n ∈ A. f (n) = m.

Leonardo Reis DCC055

Cardinalidade de Z+ e Z
1 Os conjuntos Z+ e Z têm a mesma cardinalidade?
2 Seja a função f : Z+ → Z definida como:
n
se n for par
(
2
f (n) =
1−n
2
se n for ímpar

Prove que f é uma função bijetora.

Relembrando Funções Bijetoras

Como mostrar que uma função f : A → B é bijetora?
1 provar que é injetora: se f (a1 ) = f (a2 ), então a1 = a2 ; e
2 provar que é sobrejetora: ∀m ∈ B ∃n ∈ A. f (n) = m.

Leonardo Reis DCC055

Cardinalidade de Z+ e Z

Leonardo Reis DCC055

Conjuntos Enumeráveis
Definição de Conjuntos Enumeráveis e Conjuntos Contáveis
Um Conjunto A é chamado de enumerável se Z+ ∼ A. Um conjunto é dito ser contável se é finito ou enumerável.

Teorema
Seja A um conjunto. As seguintes afirmações são equivalentes:
A é contável;
A = 0/ ou existe uma função f : Z+ → A sobrejetora;
Existe uma função f : A → Z+ injetora.

Aplicação do Teorema
Para mostrar que um conjunto A é enumerável, basta mostrar que:
1 existe uma função sobrejetora Z+ → A; ou
2 existe uma função injetora A → Z+ .

Leonardo Reis DCC055

Procedimento de Enumeração
Definição: Seja L uma linguagem sobre Σ. Uma MT M = (E , Σ, Γ, ⟨, ⊔, δ , i , {f }) é dita ser um
procedimento de enumeração de L se para toda palavra s ∈ Σ∗ existe n ∈ N tal que:
n
[i , ⟨⊔] ⊢ [f , ⟨s]

Exemplo: Construa uma MT que enumera a linguagem L = {an bn | n ≥ 1}

Leonardo Reis DCC055

Enumeração e Linguagens
Linguagens recursivas e enumeração
Se L é uma linguagem recursiva, então existe uma MT que a enumera.
Ideia da prova:
▶ gera cada palavra de Σ∗ ;
▶ testa se a palavra está na linguagem, enumerando-a em caso afirmativo.

Leonardo Reis DCC055

Enumeração e Linguagens
Linguagens recursivas e enumeração
Se L é uma linguagem recursiva, então existe uma MT que a enumera.
Ideia da prova:
▶ gera cada palavra de Σ∗ ;
▶ testa se a palavra está na linguagem, enumerando-a em caso afirmativo.

Leonardo Reis DCC055

Enumeração e Linguagens
Linguagens recursivamente enumeráveis e enumeração
L é uma linguagem recursivamente enumerável se, e somente se, existe uma MT que a enumera
(→):
▶ gera cada palavra de Σ∗
▶ avança um passo no processamento de cada palavra já gerada
▶ enumera a palavra caso esteja em L
(←):
▶ testa se a entrada com a palavra gerada pelo MT enumeradora

Leonardo Reis DCC055

Enumeração e Linguagens
Linguagens recursivamente enumeráveis e enumeração
L é uma linguagem recursivamente enumerável se, e somente se, existe uma MT que a enumera
(→):
▶ gera cada palavra de Σ∗
▶ avança um passo no processamento de cada palavra já gerada
▶ enumera a palavra caso esteja em L
(←):
▶ testa se a entrada com a palavra gerada pelo MT enumeradora

Leonardo Reis DCC055

Enumeração e Conjuntos Enumeráveis

Toda LRE é enumerável?

Σ∗ é enumerável?

Leonardo Reis DCC055

Teorema de Cantor e Linguagens
Teorema
O Conjunto P(Z+ ) não é contável.

Ideia da prova: mostrar que não existe função f : Z+ → P(Z+ ) que seja sobrejetora
▶ achar um elemento, D de P(Z+ ) que para qualquer função f e número natural n, f (n) ̸= D.

n \ f (n ) 1 2 3 4 5 ...
1 yes no no yes no ...
2 yes yes no no yes ...
3 no no no yes yes ...
4 yes no yes no no ...
5 no yes yes yes yes ...
.. .. .. .. .. .. ..
. . . . . . .
n ∈ D? no no yes yes no ...

Leonardo Reis DCC055

Teorema de Cantor e Linguagens

Leonardo Reis DCC055

Conjunto das Máquinas de Turing

O conjunto que contém todas as MTs é enumerável?

Leonardo Reis DCC055

Representação de Máquinas de Turing

Codificar MT com os símbolos do alfabeto {0, 1}

▶ O símbolo 1 é usado para codificar estados, transições e símbolos do alfabeto;
▶ O símbolo 0 é usado como separador.
Fixamos a codificação dos símbolos ⟨, ⊔ e do estado inicial
Codificação de uma MT M = (E , Σ, Γ, ⟨, ⊔, δ , i , F ):
▶ Máquina: R ⟨F ⟩00R ⟨δ ⟩
▶ Cada transição: R ⟨e ⟩0R ⟨a⟩0R ⟨e ′ ⟩0R ⟨a′ ⟩0R ⟨d ⟩

Exemplo:
a /a D

1 2
b /b E

Leonardo Reis DCC055

A Linguagens das Máquinas de Turing

Teorema
O Conjunto das Másquinas de Turing é enumerável
Ideia da prova:
▶ enumera a próxima palavra de {0, 1}∗ ;
▶ verifica se a palavra é uma representação válida de MT e, enumera-a, em caso positivo

Leonardo Reis DCC055

A Linguagens das Máquinas de Turing

Teorema
O Conjunto das Másquinas de Turing é enumerável
Ideia da prova:
▶ enumera a próxima palavra de {0, 1}∗ ;
▶ verifica se a palavra é uma representação válida de MT e, enumera-a, em caso positivo

Leonardo Reis DCC055

A Linguagem da Diagonalização

Seja LD a linguagem:
LD = {w ∈ {0, 1}∗ | w ∈
/ L(w )}

LD é uma linguagem recursivamente enumerável?

Leonardo Reis DCC055

A Linguagem da Diagonalização

Leonardo Reis DCC055