Exercícios Autômatos Finitos Determinísticos - AFD - Teoria da Computação

Quais os elementos que compõem um autômato finito Conjunto de estados Estado inicial Mapa de strings Conjunto de estados obrigatórios Linguagem Função de transição Alfabeto Conjunto de estados de aceitação Considere um AFD tal que o conjunto de estados seja dado por Q q0 q1 q2 q3 q4 e o alfabeto seja A 0 1 Quantos elementos teremos na função de transição deste autômato 2 3 5 7 10 Infinitos elementos Qual das opções contém apenas strings pertencentes à linguagem que o autômato da figura abaixo reconhece 101110011111001110 011100101101010111 001101010100111100 011001010101011010 001101110000101110 001100011100001111 Qual das opções a seguir apresenta uma afirmativa falsa Um autômato deve ter uma quantidade finita de elementos no alfabeto Um autômato deve ter apenas um único estado inicial Um autômato deve ter uma quantidade finita de estados Um autômato deve ter capacidade de reconhecer apenas uma quantidade finita de strings de uma linguagem Um autômato deve ter uma quantidade finita de transições mapeadas pela função de transição Tomando as strings aceitas pelo autômato a seguir qual a menor quantidade de ocorrências possível do símbolo mais recorrente 1 2 3 4 5 Não é possível determinar a quantidade mínima de símbolos repetidos em uma string pertencente à linguagem reconhecida pelo autômato Selecione a alternativa verdadeira sobre a linguagem reconhecida pelo autômato representado na figura abaixo A linguagem reconhecida tem uma quantidade finita de elementos Se trocarmos qualquer dos símbolos p e n em uma string pertencente à linguagem reconhecida por obteremos uma nova string que também pertencerá à linguagem reconhecida desde que seja feita a concatenação de uma string pp ou nn no final desta Todas as strings pertencentes à linguagem reconhecida possuem quantidade par de símbolos Se trocarmos todos os símbolos p e n por n e p respectivamente em uma string pertencente à linguagem reconhecida obteremos uma nova string que também pertencerá à linguagem reconhecida As strings da linguagem reconhecida não apresentam símbolos repetidos Todas as strings pertencentes à linguagem reconhecida possuem quantidade ímpar de símbolos Quais opções apresentam o resultado das operações A U B A B e A considerando as linguagens A abcde e B 1248 Ea1a11a12b1b11b12c1c11c12d1d11d12e1e11e12 Eabcdeaaabacadaebabbbcbdbecacbcccdce abcde1234 a1a2a3b1b2b3c1c2c3d1d2d3e1e2e3 abcde1248 a1a2a4b1b2b4c1c2c4d1d2d4e1e2e4 Qual opção contém uma expressão regular equivalente ao autômato da figura abaixo 0123 0 0123 0 123 0 0 0123 0123 0 0 0 0123 0 0123 0 0 0 0 0123 Apresente a expressão regular que reconhece a linguagem formada a partir do alfabeto 0 1 2 onde todas as strings começam com 0 ou 2 terminam com 1 e tem três ou mais dígitos Mostre que as seguintes strings 011111 0000001 0202020201 111111 00000002 200000 200001 101010101 2020202101 01 são obtidas pela expressão regular Envie um arquivo com a expressão regular e as demonstrações que comprovam a coerência da expressão regular Adicionar arquivo Questão 10 Expressão regular 0 2 012 1 011111 0 1 1 1 1 1 0000001 0 0 0 0 0 0 1 0202020201 0 2 0 2 0 2 0 2 0 1 111111 x Não reconhecida não inicia em 0 ou 2 00000002 0 0 0 0 0 0 0 2 x Não reconhecida não termina em 1 2000000 2 0 0 0 0 0 0 x Não reconhecida não termina em 1 200001 2 0 0 0 0 1 101010101 x Não reconhecida não inicia em 0 ou 2 2020202101 2 0 2 0 2 0 2 1 0 1 01 0 1 x Não reconhecida não possui três dígitos Questão 10 Expressão regular 0 2 012 1 011111 0 1 1 1 1 1 0000001 0 0 0 0 0 0 1 0202020201 0 2 0 2 0 2 0 2 0 1 111111 x Não reconhecida não inicia em 0 ou 2 00000002 0 0 0 0 0 0 0 2 x Não reconhecida não termina em 1 2000000 2 0 0 0 0 0 0 x Não reconhecida não termina em 1 200001 2 0 0 0 0 1 101010101 x Não reconhecida não inicia em 0 ou 2 2020202101 2 0 2 0 2 0 2 1 0 1 01 0 1 x Não reconhecida não possui três dígitos Questão 1 Conjunto de estados Estado inicial Função de transição Alfabeto e Conjunto de estados de aceitação Questão 2 10 Questão 3 001101110000101110 Questão 4 q2 Questão 5 Um automato deve ter a capacidade de reconhecer apenas uma quantidade finita de strings de uma linguagem Questão 6 3 Questão 7 Se trocarmos todos os símbolos p e n por n e p respectivamente em uma string pertencente à linguagem reconhecida obteremos uma nova string que também pertencerá à linguagem reconhecida Questão 8 Eabcdeaaabacadarbabbbcbdbecacbcccdce abcde12348 a1a2a4b1b2b4c1c2c4d1d2d4e1e2e4 Questão 9 0 123 0 0 0 1 2 3 Questão 1 Conjunto de estados Estado inicial Função de transição Alfabeto e Conjunto de estados de aceitação Questão 2 10 Questão 3 001101110000101110 Questão 4 q2 Questão 5 Um automato deve ter a capacidade de reconhecer apenas uma quantidade finita de strings de uma linguagem Questão 6 3 Questão 7 Se trocarmos todos os símbolos p e n por n e p respectivamente em uma string pertencente à linguagem reconhecida obteremos uma nova string que também pertencerá à linguagem reconhecida Questão 8 Eabcdeaaabacadarbabbbcbdbecacbcccdce abcde12348 a1a2a4b1b2b4c1c2c4d1d2d4e1e2e4 Questão 9 0 123 0 0 0 1 2 3