Teoria da Computação

Atividade Contínua 01 Teoria da Computação Quantos elementos há no conjunto C tal que C A U B Considere A 1 2 3 4 5 e B 1 3 5 7 9 5 7 8 9 10 Abaixo são feitas afirmações sobre funções Analiseas e responda I Dada uma função fx y denominamos o conjunto que contém os elementos x como domínio II Em uma função fx y os valores de y podem ser diferentes para um mesmo valor de x III Não é possível criar funções onde o domínio seja o conjunto dos números reais e a imagem seja o conjunto dos números inteiros IV Se fx x podemos afirmar que tanto o domínio quanto a imagem da função correspondem ao mesmo conjunto V As funções somente podem ser definidas se os conjuntos de domínio e imagem foram numéricos É correto apenas o que se afirmar em II e V apenas I III e IV apenas II IV e V apenas IV e V apenas I e IV apenas Qual deve ser a operação entre strings utilizada para produzir a string abcxyz a partir das strings a abc e x xyz comparação entre a e x adição entre a e x concatenação entre a e x adição entre x e a concatenação entre x e a Qual dos seguintes elementos que compõem os autômatos finitos está incorretamente definido Σ determina o conjunto de símbolos ou caracteres que podem ser utilizados na elaboração das strings que o autômato é capaz de processar q0 corresponde ao estado em que o autômato se encontra ao final do processamento de uma string Q corresponde ao conjunto de todos os estados possíveis de um autômato os quais caracterizam a condição do autômato em um dado momento permitindo que este avance no sentido de aceitar ou rejeitar uma dada string F corresponde ao conjunto de estados que indicam que o padrão desejado foi identificado na string δ é uma função que determina como o autômato muda de um estado para outro de acordo com cada símbolo da string Qual das opções a seguir contém uma ou mais strings que não são aceitas pelo autômato representado do diagrama abaixo Diagrama apresentando o autômato iniciando o processo pelo estado inicial q0seta indicando o círculo simples onde se a string processa o caractere de entrada a o próximo estado será q0 e se a string processa o caractere de entrada b o próximo estado será q1duplo círculo A imagem também apresenta a sequência do processamento da string no estado q1 onde se o caractere de entrada for b próximo estado será q1 e se caso o caractere de entrada seja a o próximo estado será q0 aab bb bb bab baab ab aaab abab bbba bbab Considerando o alfabeto Σ a b qual das opções a seguir contém apenas strings que pertencem à linguagem L ab abab ababab abababab ab aba abab aa bb ab ab abab abababab ababaab ababbab babab aba bab abab Considerando o alfabeto Σ 0 1 2 e os conjuntos A 0 1 e B 2 qual das opções a seguir contém apenas strings geradas pela expressão regular A B 12 22 0121 02 002 112 012 0122 210 102 Qual das opções a seguir corresponde à expressão regular relacionada ao autômato cujo diagrama está apresentado abaixo Diagrama apresentando o autômato iniciando o processo pelo estado inicial q0seta indicando o círculo simples onde se a string processa o caractere de entrada a o próximo estado será q1duplo círculo e se a string processa o caractere de entrada b ou c o próximo estado será q0 A imagem também apresenta a sequência do processamento da string no estado q1 onde se o caractere de entrada for a próximo estado será q1 e se caso o caractere de entrada for b ou c o próximo estado será q0 aabcbcaa aabcbcaa aabcbcaa abca abca Quantos estados são necessários em um AFND que reconheça a linguagem gerada pela expressão regular xyz que produz por exemplo as strings yz xyz xxyz 6 4 3 5 2 Abaixo são feitas afirmações sobre AFNDs Analiseas e responda I Toda linguagem reconhecida por um AFND também será reconhecida por um AFD II A única diferença nas definições matemáticas dos AFDs e AFNDs está na função de transição III Assim como AFNDs AFDs também podem rejeitar strings antes de processálas até o final IV Todo AFND terá menos estados que seu AFD equivalente V AFNDs são capazes de reconhecer linguagens regulares com quantidades infinitas de strings É correto apenas o que se afirmar em III e IV apenas I II e V apenas V apenas I e II apenas I II e IV apenas