Embed Size (px)
Citation preview
Módulo 3:Teoria dos Conjuntos
•UNIVERSIDADE FEDERAL DE CAMPINA GRANDE
•CENTRO DE ENGENHARIA ELÉTRICA E INFORMÁTICA
•DEPARTAMENTO DE SISTEMAS E COMPUTAÇÃO
•Professor Ulrich Schiel
Teoria dos Conjuntos
Conjunto
Uma coleção não-ordenada de objetos.
Ex.:
A = {Ana, Paulo, Maria, Jorge}
B = {5, 7, 3}
C = {buchada, anjinho, tapioca}
Z = {..., -3, -2, -1 , 0, 1, 2, 3, 4, 5, ... }
Notação:
letras maiúsculas para denotar conjuntos: A, B, Z
letras minúsculas para denotar elementos de conjuntos:
Ana A, x B, 5 B e 5 Z, 4 B.
Como descrever conjuntos?
1. Listando (total ou parcialmente) os elementos:
B = {5, 7, 3} Z = {..., -3, -2, -1 , 0, 1, 2, 3, 4, 5, ... }
2. Usando indução (recursão) para descrever como gerar os elementos do conjunto:
1. 2 P
2. se n P, então n+2 P 2. se n N, então n+1 N
3. Descrevendo uma propriedade P que caracterize seus elementos:
C = {x : x é uma sequência de duas letras do alfabeto}
P = {x : x é inteiro e divisível por 2}
A = {x : x é aluno de Matemática Discreta no período corrente}
T = {x : x é um nome de mês com exatamente 30 dias}
E = {x: x N e x < 0}
F = {x : x ≠ x}
Um conjunto singular
• Os conjuntos E e F abaixo têm uma característica comum interessante:
E = {x: x N e x < 0}
F = {x : x ≠ x}
• Não têm elementos.
• E = F = {} = (o conjunto vazio)
Um paradoxo e suas consequências
• Existem coleções que não são conjuntos?
• Cantor/Frege: C = {x / P(x)}
• Paradoxo de Russel (1901): C = {x / x x)}
Consequências:• Russel & Whitehead Principia Mathematica• Teoria dos conjuntos de Zermelo-Fraenkel: “Nenhum conjunto contém a si
mesmo”• Gödel: Incompletude da matemática “Não existe uma teoria completa e
consistente da aritmética elementar”
• Turing: Indecidabilidade do problema da parada• Church/Turing: Decidabilidade (Entscheidungsproblem): “Não existe um
algoritmo para decidir se uma expressão lógica qualquer é verdadeira ou falsa”
• Paradoxo do barbeiro: Um barbeiro que faz a barba de todos de seu bairro que não se barbeiam a si mesmo
Cardinalidade
• Os conjuntos abaixo diferem radicalmente com relação à “quantidade” de seus elementos:
T = {x : x é um nome de mês com exatamente 30 dias}
P = {x : x é par}
• T é finito e P é infinito.
→ A cardinalidade de um conjunto A, denotada por |A|, expressa o número de elementos do conjunto (se ele é finito) ou sua “ordem de grandeza” (se ele é infinito).
Ex.: |T| = 4 || = 0
|P| = |Z| = |Q| = 0
|R| = 2 0 = c
Relações entre conjuntos
• Que relação existe entre os seguintes conjuntos:
A = {2, 3, 5} e B = {1, 2, 3, 4, 5, 7} ?
• R.: todo elemento de A é elemento de B.
• Um conjunto A é dito ser subconjunto de um conjunto B, denotado
por A B, se, e somente se, todo elemento de A também é elemento
de B. Diz-se que A está contido em B
• Se A B e |A| < |B| então A é um subconjunto próprio de B (AB)
• Qual a relação entre o número 2, o conjunto {2} e o conjunto A
acima? • Pertinência: 2 A (2 pertence a A) e 2 {2} (2 pertence a {2}) • Continência: {2} A ({2} está contido em a A)
Relações entre conjuntos
• DISTINÇÃO ENTRE pertinência E continência
• Em um ambiente de classes e instâncias.
• Uma classe A é uma subclasse de B, (A B)
• Um objeto o é uma instância de uma classe A (o A)
• EXERCÍCIO: quais as relações entre
- ‘Brunna’, Alunos de MD, Alunos do CCC e
Frequentadores da sala CAA304.
Exercício
Sejam A, B e C os seguintes conjuntos:
A = {1, 7, 9, 15}
B = {7, 9}
C = {7, 9, 15, 20, {9}, B}
Verifique que:
B C
B A
A C
{9,{9}} C
A A
Igualdade de Conjuntos
→ Dois conjuntos A e B são iguais, A = B, se, e somente se, A B e B A.
• Exercícios:
1. Mostre que as relações = e são transitivas.
2. Mostre que as relações = e são reflexivas.
3. Mostre que a relação = e não é simétrica.
4. Mostre que a relação = é simétrica.
Conjunto das partes
Conjunto das partes (potência)
→ Seja S um conjunto qualquer. Então, o conjunto das partes de S, denotado por P(S) ou 2S, é o conjunto formado por todos os subconjuntos de S.
Ex.: Seja S = {1, 2}. Então, P(S) = {{1}, {2}, {1,2}, }
→ Seja S um conjunto qualquer com cardinalidade |S| = n. Então, |P(S)| = 2n.
Ex.: S = {1, 2} P(S) = {{1}, {2}, {1,2}, }
|S| = 2 |P(S)| = 4 = 22.
S = P(S) = P() = {}
|S| = 0 |P(S)| = 1 = 20.
OBSERVAÇÃO: Para todo conjunto C, |P(C)| > |C| (diagonalização de Cantor)
Logo |P(Z)| > |Z| e 0 < 2 0 = c = |R|
Operações sobre Conjuntos
• Seja S o conjunto de todos os alunos da UFCG.
• Então, qualquer conjunto de alunos da UFCG é um elemento de P(S).
• Seja A = {alunos do curso de computação} e
• seja B = {alunos do curso de engenharia elétrica}
• Seja MD = {alunos do curso de Matemática Discreta}
• Então, A, B e MD pertencem a P(S),
• Temos MD A, A S e B S e
• MD P(S), A P(S) e B P(S).
• O conjunto S é chamado de conjunto universo
Operações sobre Conjuntos
→ O conjunto formado por todos os alunos que fazem computação (A) mais os que fazem elétrica (B) também pertence à P(S) e é dito ser o conjunto união de A com B, denotado por AB.
AB = {x: x A ou x B}
→ O conjunto formado por todos os alunos que fazem computação (A) e elétrica (B) também pertence a P(S) e é dito ser o conjunto interseção de A com B, denotado por AB.
A B = {x: x A e x B}.
→ O conjunto de todos alunos que não fazem computação (A), é o complemento de A, denotado por A’:
A’ = {x: x S e x A}
Operações sobre Conjuntos→ Sejam A e B conjuntos quaisquer. A diferença de A com
relação a B, denotada por A-B, é o conjunto formado por todos os elementos que pertencem a A e não pertencem a B (pertencem a B’).
A-B = {x: x A e x B}→ Se A e B são conjuntos e AB = , então, A e B são ditos
serem disjuntos.
→ Sejam A e B conjuntos. O produto cartesiano de A com B, denotado por A x B, é definido como:
A x B = {(x, y): x A e y B}Obs. (x,y) é um par ordenado. Nota: (x,y) (y,x)
Definições de par ordenado: (x,y) = {x, {x,y}} ou (x,y) = {{x,1}, {y,2}}
Existe {x,x} ? e (x,x)? Como seria o par (2,1) na segunda notação?
Produto Cartesiano
A x A = A2 = {(x,y): x A e y A}
A x A x A = A3 = {(x,y,z): x A, y A e z A}
A x A x...x A = {(x1,x2,...,xn): xiA, 1 i n}
Ex.: Sejam A = {1,2} e B = {2,4}
A2 = {(1,1), (1,2), (2,1), (2,2)}
A x B = {(1,2), (1.4), (2,2), (2,4)}
Identidades Básicas
• AB = BA AB = BA
• (AB)C = A(BC) (AB )C = A(BC
• A(BC) = (AB)(AC) A(BC) = (AB)(AC)
• A = A AU = A
• AA’ = U AA’ =
Exercício
Sejam o universo S=N (os naturais) e A, B e C os seguintes conjuntos:
A = {x: x ≥ 5}
B = {10, 12, 16, 20}
C = {x: existe y N e x = 2.y}
Quais das seguintes sentenças
são falsas (mostrar porque)?
1. B C2. A C3. {11, 12, 13} A4. {} B5. {x: x N e x < 20} B6. A7. A
•Calcule:• A-B• B-A• P(B)•(B C) – A• B (C – A)• (A’ B) - C
Exercício
Sejam A e B conjuntos quaisquer. Mostre que:
(AB’) (A’B) = se, e somente se, A = B.
Classes de Objetos Conjuntos
as instâncias de uma Classe C, |C|
Uma classe C
Uma generalização CG de C1 e C2
Uma agregaçãoA de A1, A2,..., An
Um agrupamentoAG de AE
• Um conjunto CI
• Um conjunto universal C
• CG = C1 C2, e Ci C
• A A1 x A2x...xAn
• AG P(AE)
Conjuntos Classes de Objetos
Uma Classe C com os atributos A1,..,An
Uma associação
rel entre C1 e C2
Um método m de C
• C A1 x A2x...xAn
• rel C1 x C2
• Uma função
m: UC UC, tal que
m(C) = C’
Conjuntos Contáveis e Incontáveis
• Todo conjunto finito é contável.• ou seja, podemos sempre designar um elemento
como o primeiro, s1, outro elemento como o segundo, s2, e assim por diante.
• ou seja, podemos listar seus elementos na ordem escolhida:
s1, s2, s3, ..., sn
• Esta lista representa todo o conjunto.
• Um conjunto contável é um conjunto em que podemos associar a cada elemento um inteiro
• 1,2,3,...
Conjuntos Contáveis e Incontáveis
• Um conjunto infinito, também pode ser contável:
s1, s2, s3, ...
• representa todo o conjunto.• Ex.: o conjunto dos naturais, N. Podemos indicar o
primeiro elemento, o segundo elemento, o terceiro elemento, etc. :
0, 1, 2, 3,...• A operação sucessor(x) = x+1
Conjuntos Contáveis e Incontáveis
→Um conjunto infinito contável chama-se enumerável (ou denumerável).
• Assim, para se mostrar que um conjunto é enumerável precisamos exibir um esquema de listagem ou enumeração de todos os seus elementos.
• Ex.: o conjunto Q+ dos números racionais positivos é enumerável.
Q+ é enumerável
• Sabemos que todo racional positivo pode ser escrito como uma fração de inteiros positivos.
• Podemos listar todas essas frações da seguinte forma:• as que têm numerador 1 na primeira linha, as que têm
numerador 2 na segunda linha, e assim por diante:
1/1 1/2 1/3 1/4...2/1 2/2 2/3 2/4...3/1 3/2 3/3 3/4...4/1 4/2 4/3 4/4...
. . . . ... . . . . ...
• Podemos traçar uma linha que passe por toda a matriz, começando no 1/1; e em seguida fornecer uma enumeração de todo o conjunto. Ex.: 1/3 seria o 4o. elemento da enumeração.
Conjuntos Contáveis e Incontáveis
• Existem conjuntos infinitos que não podem ser enumerados : são incontáveis/não-contáveis.
• Exemplo: o conjunto de todos os reais entre 0 e 1.
Prova: Os reais entre 0 e 1 não é contável
• Qualquer número real entre 0 e 1 pode ser escrito como um número decimal: 0.d1d2d3...
onde di {0,...9}.
• Vamos assumir que o conjunto é contável. Então, existe uma enumeração do conjunto e tal que podemos descrevê-la da seguinte forma:
• dij é a j-ésima casa decimal do í-ésimo número da enumeração:
0.d11d12d13... = n1
0.d21d22d23... = n2
0.d31d32d33... = n3
Reais entre 0 e 1 não é contável
• 0.di1di2di3... dij .. = ni
• Agora, construamos um número real p da seguinte forma:
p = 0.p1p2p3...
• pi = 5 se dii 5 e pi = 6 se dii = 5
• Portanto, p é um número real entre 0 e 1.
No entanto, p não está na enumeração!!!, pois p ni, para todo i já que pois pi dii
• Método da diagonalização de Cantor.
• P.ex. para i=3
- se d33 = 5, p3 = 6
- Se d33 5, p3 = 5, logo, em ambos os casos: p n3
Problemas de Contagem
- Quanto espaço um programa consome?
- Quantos usuários um servidor pode suportar?
- Quantas operações um determinado algoritmo envolve? => COMPLEXIDADE DE ALGORITMOS
Se resumem em determinar quantos elementos existem em um conjunto finito.
Parece fácil mas nem sempre se pode determinar com facilidade uma resposta:
Exemplo
A uma criança é permitido escolher um entre dois confeitos (vermelho e preto) e um entre três chicletes (amarelo, lilás e branco) diferentes. Quantos pares diferentes de doces a criança pode ter?
Solução: decompor tarefa de escolha em duas etapas seqüenciais: a escolha do confeito e a escolha do chiclete. A árvore abaixo ilustra a seqüência e as possibilidades:
#pares diferentes = 2 (#confeitos diferentes) x 3 (#chicletes diferentes) = 6
Princípio da Multiplicação
• Se dois eventos são seqüenciados e independentes, o número de possibilidades pode ser obtido por meio da multiplicação do número de possibilidades do primeiro evento pelo número de possibilidades do segundo evento, ou melhor:
• Se existem
• n1 possibilidades para um primeiro evento,
• n2 possibilidades para um segundo evento,...,
• nk possibilidades para um k-ésimo evento, então
• existem n1xn2x...xnk possibilidades para a sequência dos eventos.
Exemplo
A última parte dos números dos telefones contêm 4 dígitos.
Quantos números de 4 dígitos existem?
Solução:
Podemos imaginar um número de 4 dígitos como resultado de 4 escolhas sucessivas e independentes: escolha do 1o., escolha do 2o., escolha do 3o. e, por fim, escolha do 4o. dígito.
A escolha de qualquer desses dígitos envolve 10 possibilidades: 0, 1, 2, ..., 9.
Portanto, há 10.10.10.10 = 10.000 escolhas possíveis, indicando que existem 10.000 números de 4 dígitos.
Exercícios
1. Com relação ao exemplo anterior, quantos números de 4 dígitos sem repetição existem?
1. Um jogo de computador é iniciado fazendo-se seleções em cada um de três menus. O primeiro menu (número de jogadores) tem quatro opções, o segundo menu (nível de dificuldade) tem oito opções e o terceiro menu (velocidade) tem seis opções. Com quantas configurações diferentes o jogo pode ser iniciado?
1. Uma senha de usuário em um computador consiste em três letras seguidas de dois dígitos. Quantas senhas diferentes são possíveis? Considere um alfabeto de 26 letras.
Princípio da Adição
Suponha que desejamos escolher uma sobremesa dentre três tortas e quatro bolos. De quantas formas isto pode ser feito?
• Solução: Existem dois eventos: escolher uma torta (com três possibilidades) e escolher um bolo (com quatro possibilidades). No entanto, esses eventos são disjuntos, ou seja, um ou outro deve acontecer, pois desejamos apenas uma sobremesa. Então, o número de possibilidades é o número total de opções que temos: 3 + 4 = 7.
Princípio da Adição
• Se A e B são eventos disjuntos com n1 e n2 possibilidades, respectivamente, então o número total de possibilidades para o evento A ou B é n1 + n2.
Exemplo
• Um cliente deseja comprar um veículo de uma concessionária que dispõe de 23 carros e 14 caminhonetas em estoque. Quantas possíveis escolhas o cliente pode ter?
• Solução: o cliente deseja escolher um carro ou uma caminhonete. São eventos disjuntos com 23 possibilidade de escolha de um carro e 14 de uma caminhonete. Pelo Princípio da Adição, a escolha de um veículo tem 23 + 14 = 27 possibilidades.
Exemplo composto
• Quantos números de 4 dígitos começam com 4 ou com 5?
• Solução: podemos considerar dois conjuntos disjuntos: números que começam com 4 e números que começam com 5.
• Para a contagem do primeiro conjunto, usamos o Princípio da Multiplicação: existe uma forma de escolher o primeiro dígito (4) e dez maneiras de escolher cada um dos outros dígitos. Portanto, são 1.10.10.10 = 1000 formas de escolher um número de 4 dígitos começando com o 4.
• Para a contagem do segundo conjunto se aplica o mesmo raciocínio dando o mesmo resultado: 1000.
• Usando agora o Princípio da Adição, podemos deduzir que existem 1000+1000 = 2000 resultados possíveis ao todo.
Exercícios
1. A, B, C e D são nodos (nós) de uma rede de computadores. Existem dois caminhos entre A e C, dois entre B e D, três entre A e B e quatro entre C e D. Por quantos caminhos uma mensagem de A para D pode ser enviada?
1. Um identificador em BASIC precisa ser uma letra simples ou uma letra seguida de outra letra ou dígito. Quantos identificadores são possíveis de serem formados?
1. Em um jantar especial existem dois aperitivos a serem escolhidos, três entradas, o menu principal e três bebidas. Quantos menus diferentes são possíveis se todos se servirem do menu principal e uma bebida mas os aperitivos e entradas são opcionais?
Princípio da Inclusão e da Exclusão
Seja S o conjunto universo e sejam A e B subconjuntos quaisquer de S:
Obs.: A-B, B-A e AB são conjuntos mutuamente disjuntos e A B = (A-B) (B-A) (AB)
Sabemos, pelo Princípio da Adição, que se C1 e C2 são conjuntos disjuntos então |C1C2| = |C1| + |C2|.
Estendendo para três conjuntos disjuntos, temos:
|A B | = |(A-B) (B-A) (AB)| = |A-B| + |B-A| + |A B|
Princípio da Inclusão e da Exclusão
|A B| = |A-B| + |B-A| + |A B|
Sabemos também que se A e B são conjuntos finitos, então |A-B| = |A| - |AB| e |B-A| = |B| - |AB|.
Então, |A B| = |A| - |A B| + |B| - |A B| + |A B|
Então,
| A B| = |A| + |B| - |A B|
Analogamente pode-se mostrar que também vale
|A B| = |A| + |B| - | A B|
Ou seja, quando contamos o número de elementos da união de A com B, precisamos contar o número de elementos em A e o número de elementos em B, mas devemos “excluir” (subtrair) os elementos que pertencem a A B para evitar contá-los duas vezes.
Exemplo
• Um vendedor oferece 2 produtos e 35 pessoas compraram. Destes 14 compraram o produto 1 e 26 o produto 2. Quantos compraram ambos?
• Solução: Seja A o conjunto das pessoas que escolheram o produto 1 e B o conjunto dos que escolheram o produto 2:
• | A B | = 35, |A| = 14, |B| = 26
• Mas, |AB| = |A| +|B| - | A B | = 14 + 26 – 35 = 5
• Portanto, 5 entrevistados escolheram ambos os produtos.
Princípio da Inclusão e da Exclusão
Estendendo para 3 conjuntos:
|A B C| = | A (B C)|
= |A| + |B C| - |A (B C)|
= |A| + |B| + |C| - |B C| - |(A B) (A C)|
= |A| + |B| + |C| - |B C| - (|A B| + |AC| - |A B C|)
= |A| + |B| + |C| - |A B| - |A C| - |BC| + |A B C|
|A B C| = |A| + |B| + |C| - |A B| - |A C| - |BC| + |A B C|
Princípio da Casa de Pombo
Se mais do que k itens são distribuídos entre k caixas, então pelo menos uma caixa conterá mais de um ítem.
Ex.: Quantas pessoas precisam estar nesta sala para que pelo menos duas pessoas têm seus nomes iniciados pela mesma letra?
Solução: Existem 26 letras no alfabeto (caixas). Se tiverem 27 pessoas, então haverá 27 letras iniciais (itens) que devem ser distribuídas entre as 26 caixas.
Exercícios
1. Quantas vezes dois dados precisam ser lançados para termos certeza que obtivemos algum par duas vezes? (Sugestão: divida as soluções em dois casos:
1. Quando os dados tiverem o mesmo valor
2. Quando os valores forem diferentes)
2. Uma pesquisa dentre 150 estudantes revelou que 83 são proprietários de carros, 97 possuem bicicletas, 28 têm motocicletas, 53 são donos de carros e bicicletas, 14 têm carros e motocicletas, sete possuem bicicletas e motocicletas, e dois têm todos os três.
Quantos estudantes possuem apenas bicicletas?
Quantos estudantes não têm qualquer dos três?
Exercícios em sala
1. Quantas vezes dois dados precisam ser lançados para termos certeza que obtivemos algum par duas vezes?
(Sugestão: divida as soluções em dois casos:
• Quando os dados tiverem o mesmo valor
• Quando os valores forem diferentes)
2. Em um jantar especial existem dois aperitivos, seguidos por três entradas, o menu principal e três bebidas. Quantos menus diferentes são possíveis se todos se servirem do menu principal e uma bebida mas os aperitivos e entradas são opcionais?
Seqüências
→ Uma seqüência ou sucessão (ou conjunto ordenado) S é uma lista de objetos que são enumerados segundo alguma ordem:
S = S(1), S(2), ..., S(n), S(n+1), ...
onde S(k), k≥1, denota o k-ésimo elemento de S.
Ex.: S = 2, 4, 8, 16, 32, ... e S(1) = 2 , S(2) = 4
As seqüências podem ser finitas ou infinitas.
Ex.: A = 1,2,3,4,5,... B = 2,4 ou (2,4)
C = b,a,n,a,n,a D = b,o,l,a ou (b,o,l,a)
O comprimento de uma seqüência é o número de elementos da seqüência:
Ex.: |C| = 6 |B| = 2 |D| = 4
Seqüências
→ DEFINIÇÃO:
→ Uma seqüência (S, I, ) é dada por
→ Um conjunto S, chamado de tipo,
→ I = N ou I = [1,2,..,n] para um dado n
→ Uma função : I ->S que determina a ordem dos termos em S.
→ Notação: (s1, s2 ,.., sn, ..), com si S e (i)= si
• é injetiva?• Os números reais R são uma sequência?
Seqüências
→ EXEMPLO:
→ Dada a sequência b a n a n a, temos
→ S = {b,a,n}
→ I = [1,2,3,4,5,6]
→ : I ->S é dada por:
→ (1)= bi (2)= ai (3)= ni (4)= ai (5)= ni (6)= ai
Seqüências
Duas seqüências A e B são iguais, A = B, se e somente se, seus termos respectivos são iguais, ou seja A(1)=B(1), A(2)=B(2), ..., A(n) = B(n).
A seqüência nula é a seqüência sem elementos ou de comprimento igual a 0 e denotada por (|| = 0).
Um par ordenado (de números) é uma seqüência de comprimento igual a 2. I = [1,2] .
Operações com sequências/palavras
Se u = a1a2...an e v = b1b2...bm então a concatenação de u com v, u.v ou u||v, é definida como:
u.v = a1a2...anb1b2...bm
Obs1.: |u.v| = |u| + |v| = n+m
Obs2.: u0 = u1 = u u2 = u.u
un = u.u...u
Operações com palavras
A inversa (ou reversa ou transposta) de uma palavra é definida como:
1. R = 2. (u,a)R = (a.u)
Exemplo: מאטימאטיקאR = א ק יטאמ יטאמ Exercício: Mostre que para todo u *:
1. (uR) R = u,
2. |uR| = |u|
• Como seria definida uma sub-cadeia (substring)?• E outras operações de extração, inserção de termos ou subcadeias?
Seqüências – aplicações
Teoria dos conjuntos: produto cartesiano Geometria analítica: para representar pontos no
plano ou no espaço. Álgebra vetorial – um vetor é uma sequência de
componentes Bancos de dados – uma instância de um banco de
dados é uma sequência de valores de atributos. Linguística –
Palavra = seq. de letras Frase = seq. de palavras Parágrafo = seq. de frases Texto = seq. de parágrafos
Alfabeto e Palavras
Um alfabeto (geralmente denotado por ) é qualquer conjunto finito não vazio de símbolos (ou letras).
Ex.: 1 = {a,b,c,...,z} 2 = {0,1}
3 = 1 2 {!, @, #, $, %, &, *, (, ), +, ^, ~, ´, `, <, >, :, ...}
Ex.: 4 = { ,ג ,ב ,א ,ש,.., ד ת } = {Aleph, Beth, Gimel , .. , Schin, Taw}
Uma palavra (ou cadeia de caracteres, ou string) é qualquer seqüência finita de símbolos de um alfabeto.
akitamitaM (= Matimatika-1) em 4 = מאטימאטיקא
Ex.: b,a,n,a,n,a ou (b,a,n,a,n,a) ou banana
1,0,1 ou (1,0,1) ou 101
Linguagens
Sejam 0, 1, 2, ..., k, k+1 , ..., os seguintes conjuntos de palavras no alfabeto : 0 = { palavras w em : |w| = 0} 1 = {palavras w em : |w| = 1} 2 = {palavras w em : |w| = 2}
k = {palavras w em : |w| = k} k+1 = {palavras w em : |w| = k+1}
Então, podemos definir * = 0 1 2 ... k k+1 ...
ou seja, * é o conjunto de todas as palavras em .
Linguagens
Ex.: = {0, 1}. Então, *= {, 0, 1, 00, 01, 10, 11, 000,...}
→ Uma linguagem L em um alfabeto é qualquer sub-conjunto de *, ou seja, L*.
→ Ex.: para = {0, 1}, podemos ter
L1 = {00, 11}
→ L2 = {1, 01, 11, 001, 011, 101, 111, 0001,...}
→ L3 = {, 0, 1, 00, 01, 10, 11, 000,...}
Gramáticas
→ Uma linguagem é usada para formar frases ou sentenças.
→ Uma sentença é uma sequência válida de palavras de acordo com uma gramática
→ uma gramática é uma estrutura G = < , L, P>
→de frases de uma linguagem L, →de um alfabeto = tnt de símbolos terminais (t) e
não-terminais (nt).→definidas por um conjunto P de regras
que substituem símbolos não terminais em por
OBS.: As palavras em L só contém símbolos terminais
Gramáticas
Exemplo:.
→Sentença frase-subst frase-verbo→ frase-subst artigo substantivo→ frase-verbo verbo advérbio→ artigo a → substantivo vaca-marinha → verbo fala → advérbio espalhafatosamente |
• Quem seríam e L neste exemplo?
GramáticasExemplo:.Seja a gramática G = < , L, P>, com
= tnt , t = {0,1}, nt= {S},
L= t* e as produções
P = { S 0S, S 1}
a) Quais sentenças válidas são produzidas por esta gramática?
b) E se acrescentarmos a produção S S0?
a) As sentenças válidas são 1, 01, 001, 0001, 00001, ...
b) Agora temos 1, 01, 001, 0001, ...
e 10, 100, 1000, ...
e 010, 0010, 00010, ...
Ou seja, todas cadeias com um ‘1’ e restante ‘0’s.
Gramáticas
Exemplo:.Seja a gramática G = < , L, P>, com
= tnt , t = {a,b,c}, nt= {S,B,C},
L= t* e as produções P = { 1.S aSBC, 2.S aBC, 3.CB BC,
4.aB ab, 5.bB bb, 6.bC bc, 7.cC cc}
As sentenças válidas em G são anbncn ?
• Verificar se a2b2c2 é uma sentença válida
Verificação se uma cadeia pertence à linguagem
Gramáticas - Exercício
Exemplo:.Seja a gramática G = < , L, P>, com = nt t
t = {0,1}, nt={S} e
as produções {P1: S 0S, P2:S S0 e P3: S 1}
Quais sentenças válidas são produzidas por esta gramática?
temos 1, 01, 001, 0001, ... e 10, 100, 1000, ... e 010, 0010, 00010, ...
Ou seja, todas cadeias com um ‘1’ e restante ‘0’s.
Gramáticas - Exercício
Considere a gramática: G = <∑, L, R >. Onde: = {+, -, .,1, 2, 3, 4, 5, 6,7, 8, 9 ,0} U {B, S, I, P, F}, sendo B
o símbolo inicial.R = {(1) B SIPF;
(2) S +|-| λ; (3) I ID | D;
(4) P . ;(5) F DD ;(6) D 0|1| 2| 3| 4| 5| 6|7| 8| 9 }
•Qual a linguagem que esta gramática define?•Mostre como ela reconhece o número -459.33•Modifique a gramática para que os números não tenham zeros a
esquerda.
Considere a gramática: G = <∑, L, R >. Onde: = {+, -, .,1, 2, 3, 4, 5, 6,7, 8, 9 ,0} U {B, S, I, P, F}, sendo B o símbolo inicial.R = {B SIPF, S +|-| λ I ID | D
P .F DDD 0|1| 2| 3| 4| 5| 6|7| 8| 9 } •Qual a linguagem que esta gramática define?RESP: esta gramática reconhece números com duas casas decimais podendo ter um sinal na frente ou não. Os
números poderão começar com um ou mais dígitos ‘0’. Em outras palavras, reconhece sequencias da forma +nn...n.nn ou –n...n.nn ou nn...n.nn.
•Mostre como ela reconhece o número -459.33RESP: para testar, basta seguir, em ordem inversa, as regras até chegar a B. Ou seja, temos:-459.33 -459.DD -459.F -459PF -45DPF -4DDPF -DDDPF SDDDPF SIDDPF SIDPF
SIPF B (N.B. também pode-se percorrer o caminho inverso)•Modifique a gramática para que ela reconheça números inteiros, sem frações.RESP:Para reconhecer só números inteiros, deve-se alterar a primeira regra para BSI e excluir as regras P . e
F DDPara reconhecer também números inteiros, a primeira regra fica sendo BSIPF | SI
