Teoria da Computação

Qual a expressão regular correspondente ao AFND abaixo Diagrama iniciando o processo pelo estado q0seta indicando o círculo simples onde se a string processa o caractere de entrada a ou b o próximo estado será q0 mas se a string processa o caractere b o próximo estado poderá ser q1duplo círculo abb ab abb ab abb Abaixo são feitas afirmações sobre expressões regulares e a biblioteca re Analiseas e responda I As expressões regulares utilizadas na biblioteca re somente podem apresentar as operações de união concatenação e estrela II Existem operações adicionais disponíveis na biblioteca re que facilitam o desenvolvimento de aplicações com expressões regulares por exemplo III A biblioteca re é utilizada apenas para estudo não sendo possível empregála em uma aplicação comercial É CORRETO apenas o que se afirmar em II apenas I e II apenas I apenas III apenas I e III apenas Qual das seguintes linguagens não pode ser reconhecida pela biblioteca re abn n 0 anbn n 0 alb n 0 abm n 0 e m 0 aban n 0 Qual string não pode ser gerada pela GLC abaixo G N A Σ 0 1 R A 0A0 A 1A1 A 00 A 11 A 0 A 1 S A 0110 000 0100 101 0 Abaixo são feitas afirmações sobre LLCs e GLCs Analiseas e responda I As GLCs podem gerar linguagens regulares II Toda linguagem regular também é uma LLC III Há LLCs que não são linguagens regulares É CORRETO apenas o que se afirmar em I II e III I e II apenas II apenas III apenas I apenas Qual item está definido incorretamente para autômatos com pilha Σ Γ Q q0 F δ Alfabeto de Entrada Σ Conjunto de Estados de Aceitação F Alfabeto da Pilha Γ Conjunto de Estados Q Estado inicial δ Qual das strings é aceita pelo ACP abaixo Diagrama iniciando o processo pelo estado inicial q0seta indicando o duplo círculo onde se ε for o símbolo lido da string processado e o símbolo esperado no topo da pilha e for o símbolo a ser inserido no topo da pilha o próximo estado será q1círculo simples No estado q1círculo simples se 0 for o símbolo lido da string processando e 0 símbolo esperado no topo da pilha e for o símbolo a ser inserido no topo da pilha o próximo estado será q1círculo simples mas se 1 for o símbolo lido da string processando 0 o símbolo esperado no topo da pilha e ε for o símbolo a ser inserido no topo da pilha o próximo estado será q2círculo simples Já no estado q2círculo simples se 1 for o símbolo lido da string processando 0 o símbolo esperado no topo da pilha e ε for o símbolo a ser inserido no topo da pilha o próximo estado será q2círculo simples mas se ε for o símbolo lido da string processando o símbolo esperado no topo da pilha e ε for o símbolo a ser inserido no topo da pilha o próximo estado será q3duplo círculo 001 010 011 0011 0110 Como uma gramática livre de contexto pode gerar frases em linguagem natural Através de um modelo horizontal de organização das palavras Através de um modelo sequencial de organização das palavras Através de um modelo hierárquico de organização das palavras Através de um modelo aleatório de organização das palavras Através de um modelo de organização das palavras em paralelo Qual das frases a seguir não pode ser gerada pela gramática abaixo G N frase sujeito predicado verbo artigo substantivop substantivos Σ o um cliente carro locou reservou R frase sujeito verbo predicado sujeito artigo substantivos predicado artigo substantivop artigo o artigo um substantivos cliente substantivop carro verbo locou verbo reservou S frase a cliente reservou um carro o cliente locou o carro um cliente locou o carro o cliente locou um carro o cliente reservou o carro Qual a expressão regular correspondente ao AFND abaixo Diagrama iniciando o processo pelo estado q0 seta indicando o círculo simples onde se a string processa o caractere de entrada a ou b o próximo estado será q0 mas se a string processa o caractere b o próximo estado poderá ser q1 duplo círculo abb ab abb ab abb Abaixo são feitas afirmações sobre LLCs e GLCs Analiseas e responda I As GLCs podem gerar linguagens regulares II Toda linguagem regular também é uma LLC III Há LLCs que não são linguagens regulares É CORRETO apenas o que se afirmar em I II e III I e II apenas II apenas III apenas I apenas Qual é o tipo da estrutura de dados presente em autômatos com pilha FIFO first in first out FILO first in last out O correto tecnicamente seria LIFO mas se considerarmos o fluxo é equivalente a FILO FIPO first in parallel out FISO first in structured out FIRO first in randomly out Abaixo são feitas afirmações sobre expressões regulares e a biblioteca re Analiseas e responda I As expressões regulares utilizadas na biblioteca re somente podem apresentar as operações de união concatenação e estrela II Existem operações adicionais disponíveis na biblioteca re que facilitam o desenvolvimento de aplicações com expressões regulares por exemplo III A biblioteca re é utilizada apenas para estudo não sendo possível empregála em uma aplicação comercial É CORRETO apenas o que se afirmar em II apenas I e II apenas I apenas III apenas I e III apenas Qual das seguintes linguagens não pode ser reconhecida pela biblioteca re abn n 0 anbn n 0 anb n 0 anbm n 0 e m 0 aban n 0 Em tese TODAS AS LINGUAGENS listadas já são reconhecidas pela biblioteca re por conta de funções adicionais implementadas Qual string não pode ser gerada pela GLC abaixo G N A Σ 0 1 R A 0A0 A 1A1 A 00 A 11 A 0 A 1 S A 0110 000 0100 101 0 Qual item está definido incorretamente para autômatos com pilha Σ Γ Q q0 F δ Alfabeto de Entrada Σ Conjunto de Estados de Aceitação F Alfabeto da Pilha Γ Conjunto de Estados Q Estado inicial δ Qual das strings é aceita pelo ACP abaixo Diagrama iniciando o processo pelo estado inicial q0seta indicando o duplo círculo onde se ε for o símbolo lido da string processado e o símbolo esperado no topo da pilha e for o símbolo a ser inserido no topo da pilha o próximo estado será q1círculo simples No estado q1círculo simples se 0 for o símbolo lido da string processando ε o símbolo esperado no topo da pilha e for o símbolo a ser inserido no topo da pilha o próximo estado será q1círculo simples mas se 1 for o símbolo lido da string processando 0 o símbolo esperado no topo da pilha e ε for o símbolo a ser inserido no topo da pilha o próximo estado será q2círculo simples Já no estado q2círculo simples se 1 for o símbolo lido da string processando 0 o símbolo esperado no topo da pilha e ε for o símbolo a ser inserido no topo da pilha o próximo estado será q2círculo simples mas se ε for o símbolo lido da string processando o símbolo esperado no topo da pilha e ε for o símbolo a ser inserido no topo da pilha o próximo estado será q3duplo círculo 001 010 A inserção de um 4o símbolo pode conduzir à string 0010 que seria também aceita 011 0011 0110 Como uma gramática livre de contexto pode gerar frases em linguagem natural Através de um modelo horizontal de organização das palavras Através de um modelo sequencial de organização das palavras Através de um modelo hierárquico de organização das palavras Através de um modelo aleatório de organização das palavras Através de um modelo de organização das palavras em paralelo Qual das frases a seguir não pode ser gerada pela gramática abaixo G N frase sujeito predicado verbo artigo substantivop substantivos Σ o um cliente carro locou reservou R frase sujeito verbo predicado sujeito artigo substantivos predicado artigo substantivop artigo o artigo um substantivos cliente substantivop carro verbo locou verbo reservou S frase a cliente reservou um carro o cliente locou o carro um cliente locou o carro o cliente locou um carro o cliente reservou o carro