Linguagens Formais e Automatos - conjuntos e grafos

Prévia do material em texto

Linguagens Formais e 
Autômatos
Prof. Marcio Klein
Curso da Ciência da Computação
Bem vindo à
Informações
Ementa
 Fundamentos de 
Matemática
 Alfabetos e Palavras
 Linguagens e 
Gramática
 Autômatos e Máquina 
de Turing
➢ Bibliografia
➢ Diverio, T. A.; Menzes, 
P. B.; Teoria da 
Computação; Bookman
➢ Menezes, P. B.; 
Linguagens Formais e 
Autômatos; Bookman
➢ Sipser, M.; Introdução 
à Teoria da 
Computação; Thomson
Prof. Marcio Klein 2018_1
Fundamentos Matemáticos
Prof. Marcio Klein 2018_1
Conjuntos
Relações entre conjuntos
Funções
Indução
Grafos
Árvores
Conjuntos – conceitos primitivos
Prof. Marcio Klein 2018_1
 Conjunto das letras: a,b,c . . .
 Conjunto dos números inteiros (Z) : ...-2,-1,0,1,2 ...
 Conjunto dos números naturais (N): 1,2,3 .
 Dos números reais (R): inteiros e fracionários
1.Conjunto: é uma coleção de objetos
Exemplos:
2. Elementos: é cada um dos componentes do conjunto
3. Pertinência: característica associada ao elemento 
que faz parte do conjunto
Conjuntos - Notação
Prof. Marcio Klein 2018_1
Um conjunto qualquer A pode 
ser denotado por duas chaves 
limitando o conjunto:
Exemplo :
A = {a}
X = {garfo, faca} -> garfo € X
N6= {1,2,3,4,5,6}
Z = {...,-9,-3,3,9, ...}
Conjuntos - Notação
Prof. Marcio Klein 2018_1
- Representação Gráfica
Diagramas de Venn para os conjuntos A e B
➢ Por extensão
V = {a, e, i, o, u}
➢ Por compreensão: estabelece a propriedade que 
caracteriza todos os elementos do conjunto. 
Exemplos: 
AlunoUninove = {a / a é um aluno da Uninove}
Prof. Marcio Klein 2018_1
Conjuntos - Especificação
Conjunto Finto / Infinito
 Um conjunto qualquer A é finito se for possível 
especificar o conjunto por extensão (listar todos os 
seus elementos). Caso contrário, isto é, quando 
somente se pode especificar tal conjunto por 
compreensão dizemos que o conjunto é infinito.
 Exemplos: 
 A = { a, e, i, o, u } – conjunto finito
 P = { x : x € N, x é primo}
Prof. Marcio Klein 2012/1
Conjunto Inclusão (Subconjunto)
 A está contido em B, (A  B), se todos os elementos 
de A também estão em B. 
 A está propriamente contido em B (A  B) , se o 
conjunto B, além de conter os elementos de A, 
contém também outros elementos. O conjunto A é 
denominado subconjunto de B e o conjunto B é o 
superconjunto que contém A, diz-se também que A 
está incluído em B. Exemplo:
 P = { m, n } e Q = {m, n, t, u } então P  Q
Prof. Marcio Klein 2018_1
Conjunto – mais algumas definições
 Conjunto Vazio ou Nulo
 É o conjunto sem elementos denotado por { } ou 
 É o elemento neutro dos conjuntos
 Exemplo: conjunto dos satélites da lua
 Conjuntos Iguais

 Elementos Repetidos / Ordenados
 A repetição de um elemento na especificação de um 
conjunto representa um único elemento: {a,b,b} = {a,b}
 A ordem dos elementos é indiferente: {a,b} = {b,a}
Prof. Marcio Klein 2012/1
Conjunto Complemento
Prof. Marcio Klein 2018_1
Seja S = {a,b,c,d} então:
Conjunto Universal
Prof. Marcio Klein 2018_1
 Os membros do conjunto de todos os conjuntos de uma 
determinada área de aplicação, as vezes um conjunto 
muito grande, é chamado Conjunto Universal e 
denotado pela letra U.
 Exemplos:
 A = conjunto computadores pessoais
 B = conjunto Supercomputadores
 U = conjunto de todos os computadores
Conjunto Potência
 É denotado por P (A) ou 2ª e chamado também 
Conjunto das partes de A
 É o conjunto de todos os subconjuntos de A
 Importante:
 Os conjuntos  e A sempre são elementos de P (A) 
 O número de elementos de P (A) é por:
 N = 2n(A) onde n(A) é o número de elementos do conjunto A
 Exemplo:
Prof. Marcio Klein 2018_1
Conjuntos – Operações Básicas
 Reunião de Conjuntos
 A reunião dos conjuntos A e B é o conjunto de todos os elementos que 
pertencem ao conjunto A ou pertencem ao conjunto B.
 Interseção de Conjuntos
 A interseção dos conjuntos A e B é o conjunto de todos os elementos que 
pertencem ao conjunto A e pertencem ao conjunto B.
Prof. Marcio Klein 2018_1
Conjuntos – Operações Básicas
 Diferença de Conjuntos
 A diferença dos conjuntos A e B é o conjunto de todos os elementos que 
pertencem ao conjunto A e não pertencem ao conjunto B.
 Diferença Simétrica
 A diferença simétrica entre os conjuntos A e B é o conjunto de todos os 
elementos que pertencem à reunião dos conjuntos A e B e não
pertencem à interseção dos conjuntos A e B.
Prof. Marcio Klein 2018_1
Conjuntos – Operações Básicas
 Resumo das Operações Básicas 
Prof. Marcio Klein 2018_1
Conjuntos – Equivalência de
Prof. Marcio Klein 2018_1
Conjuntos – Ufa, haja conjuntos
Prof. Marcio Klein 2018_1
 1. Apresentar uma lista de três conjuntos 
especificados por extensão e três conjuntos 
especificados por compreensão.
 2. Listar os elementos dos seguintes conjuntos
 3. Quais destes conjuntos são iguais: 
 {r, s, t}, {s, t, r, s}, {t, s, t, r} e {s, r, s, t}
Conjuntos – Exercícios
Prof. Marcio Klein 2018_1
Conjuntos – Exercícios
 4. Ilustrar com os Diagramas de Venn a lei distributiva
 A  (B  C) = (A  B) (A  C)
 5. Seja X = { a, b, c } e Y = { 1 }. Listar todos os 
elementos de:
 X  Y 
 todos os subconjuntos de X  Y
Prof. Marcio Klein 2018_1
Conjuntos – Exercícios
Prof. Marcio Klein 2018_1
Conjuntos – Fim
Prof. Marcio Klein 2018_1