Atividade de Fundamentos Teoricos da Computação

Lista de Exercıcios 1 FTC Professor Julio Cesar da Silva Cotemig BHMG Leia com atencao as perguntas abaixo e responda de acordo com o conteudo visto em sala de aula Vocˆe pode enviar uma foto com as respostas escritas em um caderno ou um documento do Google Docs contendo seu nome completo Envie respostas para todas as perguntas Nao e necessario enviar as perguntas Nao envie apos o prazo limite Uma tecnica de estudo recomendada e ler os slides e suas anotacoes de aula antes de comecar a resolver os exercıcios Durante a resolucao e importante consultar os livros de referˆencia bibliografica da disciplina para enriquecer seu aprendizado Todos os exemplos e exercıcios vistos em sala de aula servem como material de estudo para a proxima avaliacao Nao se recomenda o uso de ferramentas do tipo chat GPT visto que o importante e treinar a sua capacidade de estudo e memorizacao QUESTAO 1 Mostre que as seguintes afirmativas sao validas a α β α b α α β c α β α Procure argumentar em portuguˆes como normalmente se faz em uma prova Por exemplo segue uma prova de que α β α e valida A afirmativa α β α so e falsa se α β e verdadeira e α e falsa Para que α β seja verdadeira α β tem que ser falsa e α β so e falsa se α e verdadeira e β falsa Contradicao pois α nao pode ser falsa e verdadeira Portanto α β α nao pode ser falsa logo e valida QUESTAO 2 Qual seria o esboco de uma prova para Se x 0 e x y e x e y sao numeros naturais entao x2 y2 Qual o nome do tipo de prova vocˆe usuaria e qual a justificativa para isso QUESTAO 3 Que condicao ou condicoes os conjuntos A B e C devem satisfazer para que a A B B A b A B A C c A B A C considere agora que B C d A B e A C 1 QUESTAO 4 Seja a relacao x y N2 y x2 diga se a Se essa e uma relacao reflexiva simetrica ou transitiva Justifique b Qual e o domınio contradomınio e a imagem dessa relacao c Qual a sua funcao inversa d Podemos afirmar que essa funcao e bijetora Justifique QUESTAO 5 Seja B o conjunto de todas as sequencias dos dıgitos 0 e 1 com no mınimo um dıgito Exemplos de elementos de B 0 1 00 01 10 11 000 etc E possıvel dizer se B e enumeravel isto e existe uma funcao bijetora que o enumere Justifique QUESTAO 6 Qual e o numero de prefixos sufixos e subpalavras de uma palavra de tamanho n QUESTAO 7 Seja Σ um alfabeto Prove que se x y w Σ e xw yw entao x y QUESTAO 8 Sejam A 00 11 B 01 10 e C λ 1 Calcule as seguintes concatenacoes a AA b AC c CC d ABC e ABC f AB C QUESTAO 9 O conjunto dos numeros inteiros Z e o conjunto das letras do alfabeto brasileiro podem ser alfabetos em uma linguagem formal Justifique QUESTAO 10 Em ciˆencia da computacao as informacoes que um computador processa sao representadas como sequˆencias de sımbolos pertencentes a um alfabeto especıfico Um alfabeto e um conjunto finito de sımbolos e uma palavra e uma sequˆencia finita de sımbolos desse alfabeto Por exemplo no sistema binario usamos o alfabeto Σ 0 1 e qualquer sequˆencia de 0s e 1s e uma palavra valida Agora considere um tabuleiro de xadrez de 8 8 casas onde cada casa pode ser representada por um unico bit 2 1 para casas brancas 0 para casas pretas Assim podemos representar todo o tabuleiro como uma palavra binaria de 64 bits ou como 8 palavras de 8 bits cada O tabuleiro padrao do xadrez onde a casa inferior esquerda e preta pode ser representado como 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 Agora considere a codificacao do estado do jogo onde cada casa pode conter 00 para uma casa vazia 01 para um peao 10 para bispo cavalo ou torre 11 para rainha ou rei Essa codificacao expande a representacao do tabuleiro para uma palavra de 128 bits ou 8 palavras de 16 bits Questao Dado um tabuleiro de xadrez inicial expresso na codificacao binaria simples considere que um com putador lˆe essa representacao como entrada realiza uma operacao e gera uma saıda representada na codificacao de estado do jogo a Defina formalmente o alfabeto e as palavras envolvidas na entrada e saıda do sistema b Explique como a concatenacao de palavras pode ser utilizada para armazenar todo o estado do tabuleiro c Se considerarmos que a transformacao da matriz binaria simples para a codificacao de estado do jogo pode ser realizada por um autˆomato finito quais seriam os estados e transicoes possıveis desse autˆomato d Demonstre como a palavra binaria correspondente ao estado inicial do tabuleiro pode ser proces sada para obter a saıda esperada a palavra binaria que representa o tabuleiro codificado pelo estado do jogo 3 Dica Comece identificando qual e o alfabeto de entrada e de saıda A concatenacao de palavras pode ajudar a entender como representamos um tabuleiro inteiro como uma unica sequˆencia binaria Pense na transicao entre estados do autˆomato como sendo a conversao das casas vazias e das pecas de um formato para outro Um autˆomato finito pode processar a palavra de entrada bit a bit ou em grupos de bits e produzir a saıda correspondente 4 QUESTÃO 1 a α β α Demonstração A implicação α β α só é falsa quando o antecedente α β é verdadeiro e o consequente α é falso Vamos analisar 1 Para que α β seja verdadeiro tanto α quanto β precisam ser verdadeiros 2 Se α é verdadeiro pois α β é verdadeiro então o consequente α também é verdadeiro 3 Portanto não é possível que α β seja verdadeiro e α seja falso A implicação nunca é falsa 4 Concluímos que α β α é uma tautologia sempre verdadeira b α α β Demonstração A implicação α α β é um caso clássico de ex falso quodlibet do falso tudo se segue Vamos analisar 1 O antecedente α α é uma contradição pois α não pode ser simultaneamente verdadeiro e falso 2 Como α α é sempre falso a implicação α α β é sempre verdadeira independentemente do valor de β 3 Isso ocorre porque em lógica uma implicação com antecedente falso é sempre verdadeira 4 Portanto α α β é uma tautologia c α β α Demonstração Vamos analisar a expressão α β α 1 A implicação α β é equivalente a α β 2 Substituindo na expressão original temos α β α 3 Podemos reorganizar os termos usando a propriedade associativa da disjunção α α β 4 A expressão α α é uma tautologia sempre verdadeira pois α ou α sempre será verdadeiro 5 Portanto a expressão original se reduz a Verdadeiro β 6 Como Verdadeiro β é sempre verdadeiro independentemente de β concluímos que α β α é uma tautologia QUESTÃO 2 1 Hipóteses o x0 o x y o x e y são números naturais 2 Tese o x 2 y 2 3 Passos da prova o Como x e y são números naturais e x y podemos escrever yxk onde k é um número natural maior ou igual a 1 pois x y o Substituindo yxk na expressão y 2 temos y 2xk 2x 22 xkk 2 o Como k 1 e x0 os termos 2 xk e k 2 são positivos o Portanto y 2x 22 xkk 2x 2 o Concluímos que x 2 y 2 4 Conclusão o Dadas as hipóteses a tese x 2 y 2 é verdadeira QUESTÃO 3 a ABBA Condição necessária e suficiente Para que ABBA os conjuntos A e B devem ser iguais ou seja AB Justificativa 1 AB é o conjunto de elementos que estão em A mas não em B 2 BA é o conjunto de elementos que estão em B mas não em A 3 Para que ABBA os conjuntos AB e BA devem ser vazios pois são complementares 4 Isso só ocorre se A e B forem iguais ou seja AB b A BAC Condição necessária e suficiente Para que A BAC os conjuntos B e C devem ser subconjuntos de A ou mais precisamente B e C devem diferir apenas em elementos que já estão em A Formalmente BACA Justificativa 1 A união A B inclui todos os elementos de A e B 2 A união AC inclui todos os elementos de A e C 3 Para que A BAC os elementos que B e C adicionam a A devem ser os mesmos 4 Portanto BACA c A BAC com BC Condição necessária e suficiente Para que A BAC com BC os conjuntos B e C devem diferir apenas em elementos que já estão em A Formalmente BACAe BC Justificativa 1 Como A BAC os elementos que B e C adicionam a A devem ser os mesmos ou seja BACA 2 No entanto BC o que significa que B e C podem diferir em elementos que já estão em A 3 Em outras palavras B e C podem ter elementos diferentes desde que esses elementos já pertençam a A d A B e AC Condição necessária e suficiente Para que A B e AC os conjuntos A B e C devem satisfazer 1 A é um subconjunto de B ou seja todos os elementos de A estão em B 2 A é um subconjunto próprio de C ou seja todos os elementos de A estão em C mas C contém pelo menos um elemento que não está em A Justificativa 1 A B significa que todo elemento de A também pertence a B 2 AC significa que todo elemento de A também pertence a C mas C tem pelo menos um elemento que não está em A 3 Portanto A deve ser um subconjunto de B e um subconjunto próprio de C QUESTÃO 4 a Reflexiva simétrica ou transitiva 1 Reflexiva o Uma relação é reflexiva se para todo x N x x R o No entanto x x R só ocorre se xx 2 o que é verdade apenas para x0 e x1 o Como não vale para todos os x N a relação não é reflexiva 2 Simétrica o Uma relação é simétrica se para todo x y R y xR o Se x y R então yx 2 Para que y xR teríamos xy 2 ou seja xx 2 2x 4 o Isso só ocorre para x0 e x1 Para outros valores de x x x 4 o Portanto a relação não é simétrica 3 Transitiva o Uma relação é transitiva se para todo x y R e y z R temos x z R o Se x y R então yx 2 o Se y z R então zy 2 x 2 2x 4 o Para que x z R precisamos ter zx 2 mas zx 4 Isso só ocorre se x 4x 2 ou seja para x0 e x1 o Como não vale para todos os x N a relação não é transitiva b Domínio contradomínio e imagem 1 Domínio o O domínio da relação R é o conjunto de todos os x N para os quais existe y N tal que yx 2 o Como x 2 está definido para todo x N o domínio é N 2 Contradomínio o O contradomínio da relação R é o conjunto de todos os y N que podem ser relacionados a algum x N o Como yx 2 e x N o contradomínio também é N 3 Imagem o A imagem da relação R é o conjunto de todos os y N que são quadrados de algum x N o Portanto a imagem é 014 91625 ou seja o conjunto dos quadrados perfeitos em N c Função inversa A relação R é uma função pois cada x N está associado a um único yx 2 Para que uma função tenha inversa ela deve ser bijetora injetora e sobrejetora No entanto R não é sobrejetora pois a imagem de R os quadrados perfeitos não cobre todo o contradomínio N Além disso R não é injetora pois x e x têm o mesmo quadrado mas como estamos em N isso não é um problema Portanto a função não tem inversa em N d A função é bijetora Uma função é bijetora se é injetora e sobrejetora o Injetora Sim pois para x1 x2 N se x1 2x2 2 então x1x2 o Sobrejetora Não pois a imagem de R os quadrados perfeitos não cobre todo o contradomínio N Portanto a função não é bijetora QUESTÃO 5 Para determinar se o conjunto B de todas as sequências dos dígitos 0 e 1 com no mínimo um dígito é enumerável precisamos verificar se existe uma função bijetora entre B e o conjunto dos números naturais N 1 O que é um conjunto enumerável Um conjunto é enumerável se seus elementos podem ser colocados em uma correspondência biunívoca bijetora com os números naturais N Isso significa que podemos contar os elementos do conjunto atribuindo a cada um deles um número natural único 2 Descrição do conjunto B O conjunto B é formado por todas as sequências finitas de 0 e 1 com pelo menos um dígito Exemplos de elementos de B Sequências de comprimento 1 0 1 Sequências de comprimento 2 00 01 10 11 Sequências de comprimento 3 000 001 010 011 100 101 110 111 E assim por diante 3 B é enumerável Sim B é enumerável Vamos justificar Argumento 1 Contagem das sequências por comprimento 1 Podemos organizar as sequências de B em grupos de acordo com seu comprimento o Sequências de comprimento 1 0 1 2 sequências o Sequências de comprimento 2 00 01 10 11 4 sequências o Sequências de comprimento 3 000 001 111 8 sequências o E assim por diante 2 Para cada comprimento n há 2 n sequências possíveis 3 Podemos enumerar todas as sequências de B da seguinte forma o Primeiro listamos as 2 sequências de comprimento 1 o Depois as 4 sequências de comprimento 2 o Em seguida as 8 sequências de comprimento 3 o E assim por diante 4 Como cada grupo de sequências de comprimento n é finito e há uma quantidade enumerável de grupos um para cada nN a união de todos esses grupos também é enumerável Argumento 2 Correspondência com números naturais Podemos estabelecer uma bijeção entre B e N da seguinte forma 1 Atribuímos a cada sequência um número natural único seguindo a ordem de comprimento e dentro de cada comprimento a ordem lexicográfica 0 antes de 1 Exemplo o 0 1 o 1 2 o 00 3 o 01 4 o 10 5 o 11 6 o 000 7 o 001 8 o E assim por diante 2 Essa atribuição é uma função bijetora pois cada sequência recebe um número natural único e todo número natural é atribuído a uma sequência única 4 Conclusão O conjunto B é enumerável pois podemos organizar suas sequências em uma lista infinita e estabelecer uma correspondência biunívoca com os números naturais N QUESTÃO 6 1 Prefixos Um prefixo de uma palavra é qualquer sequência inicial dessa palavra incluindo a palavra vazia e a própria palavra Para uma palavra de tamanho n os prefixos são o A palavra vazia ϵ o O primeiro caractere o Os dois primeiros caracteres o o A palavra completa todos os n caracteres Portanto o número de prefixos é n1 Exemplo Para a palavra abc n3 o Prefixos ϵ a ab abc o Total de prefixos 314 2 Sufixos Um sufixo de uma palavra é qualquer sequência final dessa palavra incluindo a palavra vazia e a própria palavra Para uma palavra de tamanho n os sufixos são o A palavra vazia ϵ o O último caractere o Os dois últimos caracteres o o A palavra completa todos os n caracteres Portanto o número de sufixos também é n1 Exemplo Para a palavra abc n3 o Sufixos ϵ c bc abc o Total de sufixos 314 3 Subpalavras Uma subpalavra ou substring de uma palavra é qualquer sequência contígua de caracteres dessa palavra incluindo a palavra vazia e a própria palavra Para uma palavra de tamanho n o número de subpalavras é dado pela soma das combinações de caracteres contíguos de todos os comprimentos possíveis de 0 a n O número de subpalavras de comprimento k 0k n é nk1 Portanto o número total de subpalavras é a soma k0 n nk1n1 nn1 1 n1 n2 2 Assim o número de subpalavras é n1 n2 2 Exemplo Para a palavra abc n3 o Subpalavras ϵ a b c ab bc abc o Total de subpalavras 31 32 2 45 2 10 QUESTÃO 7 Neste caso vamos usar a definição de concatenação de strings e argumentar por indução no comprimento de w Prova 1 Hipótese o x y wΣ o xwyw 2 Tese o xy 3 Passos da prova o Caso base w0 Se w é a string vazia wϵ então xwxϵx e ywyϵ y Como xwyw temos xy Portanto a afirmação é válida para w0 o Passo indutivo Suponha que a afirmação é válida para wk ou seja se xwyw e wk então xy Agora considere wk1 Podemos escrever w como wa w onde aΣ e w k Substituindo wa w na igualdade xwyw temos xaw yaw Pela propriedade associativa da concatenação isso equivale a xaw yaw Pela hipótese indutiva como w k temos xaya Como xaya concluímos que xy 4 Conclusão o Por indução a afirmação é válida para todo w Σ QUESTÃO 8 A concatenação de dois conjuntos X e Y denotada por XY é o conjunto de todas as strings que podem ser formadas concatenando uma string de X com uma string de Y Dados A0011 B0110 Cλ1 onde λ é a string vazia a AA AA é a concatenação de A com A AAxy x A y A Calculando 00000000 00110011 11001100 11111111 Portanto AA0000001111001111 b AC AC é a concatenação de A com C ACxy x A y C Calculando 00 λ00 001001 11 λ11 111111 Portanto AC0000111 111 c CC CC é a concatenação de C com C CCxy xC yC Calculando λ λλ λ11 1 λ1 1111 Portanto CCλ111 d ABC Primeiro calculamos AB ABxy x A y B Calculando 00010001 00100010 11011101 11101110 Portanto AB0001001011011110 Agora concatenamos AB com C ABCxyx AB yC Calculando 0001 λ0001 0001100011 0010 λ0010 0010100101 1101 λ1101 1101111011 1110 λ1110 1110111101 Portanto ABC000100011001000101110111011111011101 e A BC Primeiro calculamos BC BCxy xB yC Calculando 01 λ01 011011 10 λ10 101101 Portanto BC0101110 101 Agora concatenamos A com BC A BCxy x A y BC Calculando 00010001 0001100011 00100010 0010100101 11011101 1101111011 11101110 1110111101 Portanto A BC000100011001000101110111011111011101 f A BC Primeiro calculamos BC BC0110 λ 1 Agora concatenamos A com BC A BC xy x A y BC Calculando 00010001 00100010 00 λ00 001001 11011101 11101110 11 λ11 111111 Portanto A BC 00001000100101111111011110 QUESTÃO 9 Em teoria das linguagens formais um alfabeto é um conjunto finito e não vazio de símbolos Esses símbolos são os blocos básicos usados para construir strings palavras em uma linguagem formal Finito O alfabeto deve ter um número finito de símbolos Não vazio O alfabeto deve conter pelo menos um símbolo 1 Conjunto dos números inteiros Z O conjunto Z é infinito pois contém todos os números inteiros positivos negativos e zero Z 21012 Pode ser um alfabeto Não porque um alfabeto deve ser finito e Z é infinito Justificativa Em linguagens formais trabalhamos com alfabetos finitos para garantir que as strings palavras sejam construídas a partir de um número limitado de símbolos Um alfabeto infinito tornaria impossível definir linguagens de maneira prática e formal 2 Conjunto das letras do alfabeto brasileiro O alfabeto brasileiro é composto por 26 letras A BC D E FG H I J K L M N O PQ RS T U V W X Y Z Pode ser um alfabeto Sim porque é um conjunto finito e não vazio Justificativa O alfabeto brasileiro atende às condições necessárias para ser um alfabeto em uma linguagem formal Ele pode ser usado para construir strings palavras e definir linguagens formais como a linguagem de todas as palavras válidas em português 3 Conclusão Z Não pode ser um alfabeto pois é infinito Alfabeto brasileiro Pode ser um alfabeto pois é finito e não vazio QUESTÃO 10 a Alfabeto e palavras envolvidas na entrada e saída 1 Alfabeto de entrada Σentrada o O alfabeto de entrada é o conjunto de símbolos usados para representar as casas do tabuleiro na codificação binária simples o Cada casa é representada por 1 bit 0 casa preta 1 casa branca o Portanto o alfabeto de entrada é Σentrada0 1 2 Palavra de entrada o A palavra de entrada é uma sequência de 64 bits representando o tabuleiro de xadrez o Exemplo tabuleiro padrão 1010101001010101101010100101010110101010010101011010101001010101 3 Alfabeto de saída Σ sa ı ˊ da o O alfabeto de saída é o conjunto de símbolos usados para representar o estado do jogo o Cada casa é representada por 2 bits 00 casa vazia 01 peão 10 bispo cavalo ou torre 11 rainha ou rei o Portanto o alfabeto de saída é Σ sa ı ˊ da00011011 4 Palavra de saída o A palavra de saída é uma sequência de 128 bits representando o estado do tabuleiro o Exemplo tabuleiro inicial sem peças 0000000000000000000000000000000000000000000000000000000000000000 b Concatenação de palavras para armazenar o estado do tabuleiro A concatenação de palavras é usada para combinar as representações de cada casa do tabuleiro em uma única sequência binária No caso da entrada cada casa é representada por 1 bit e a concatenação de 64 bits forma a palavra de entrada No caso da saída cada casa é representada por 2 bits e a concatenação de 128 bits forma a palavra de saída A concatenação permite que o estado completo do tabuleiro seja armazenado e processado como uma única unidade c Autômato finito para a transformação Um autômato finito pode ser projetado para processar a palavra de entrada 64 bits e gerar a palavra de saída 128 bits Vamos definir os componentes do autômato 1 Estados Q o O autômato terá estados que representam a leitura de cada casa do tabuleiro e a geração da saída correspondente o Exemplo de estados q0 estado inicial q1 leitura de uma casa preta 0 q2 leitura de uma casa branca 1 qfinal estado final 2 Transições δ o As transições dependem do bit lido na entrada e do estado atual o Exemplo de transições δ q00q100 se a casa é preta gera 00 casa vazia δ q01q200 se a casa é branca gera 00 casa vazia O autômato pode ser estendido para incluir transições que geram 01 10 ou 11 dependendo das peças presentes 3 Saída o A cada transição o autômato gera 2 bits de saída que são concatenados para formar a palavra de saída d Processamento da palavra binária Vamos demonstrar como a palavra binária de entrada é processada para gerar a saída 1 Entrada o Tabuleiro padrão 64 bits 1010101001010101101010100101010110101010010101011010101001010101 2 Processamento o O autômato lê cada bit da entrada e gera 2 bits de saída o Para o tabuleiro inicial sem peças todas as casas são convertidas para 00 casa vazia o Exemplo Se o autômato lê 1 casa branca gera 00 Se o autômato lê 0 casa preta gera 00 3 Saída o A palavra de saída é uma sequência de 128 bits onde cada casa é representada por 00 0000000000000000000000000000000000000000000000000000000000000000 Assim a Alfabeto de entrada 01 Alfabeto de saída 00011011 b A concatenação de palavras permite representar o tabuleiro como uma única sequência binária c O autômato finito tem estados que representam a leitura de cada casa e transições que geram a saída correspondente d A palavra binária de entrada é processada bit a bit gerando a palavra de saída de 128 bits