Considere o Autômato Finito Não Determinístico (AFN) abaixo, onde A é o estado inicial e D o único estado final. Qual Autômato Finito Deterministico (AFD), com d como sua função de transição, aceita a mesma linguagem?
Estado Inicial: A
Estados Finais: C e D
d(A, b) = B
d(B, a) = C
d(C, a) = D
-----------------------
É impossível converter esse autômato finito não determinístico em um autômato finito determinístico
-----------------------
Todos os autômatos indicados em outras alternativas são equivalentes ao AFN dado
É impossível converter esse autômato finito não determinístico em um autômato finito determinístico
Todos os autômatos indicados em outras alternativas são equivalentes ao AFN dado
d(A, a) = C, d(A, b) = B, d(B, a) = C, d(B, b) = B, d(C, a) = D, d(C, b) = B, d(D, a) = D, d(D, b) = D
d(A, a) = C, d(A, b) = B, d(B, a) = C, d(B, b) = D, d(C, a) = D, d(C, b) = B, d(D, a) = D, d(D, b) = D
d(A, a) = C, d(A, b) = B, d(B, a) = C, d(B, b) = D, d(C, a) = D, d(C, b) = B, d(D, a) = C, d(D, b) = D
Estado Inicial: A
Estados Finais: C e D
d(A, b) = B
d(B, a) = C
d(C, a) = D
-----------------------
É impossível converter esse autômato finito não determinístico em um autômato finito determinístico
-----------------------
Todos os autômatos indicados em outras alternativas são equivalentes ao AFN dado
É impossível converter esse autômato finito não determinístico em um autômato finito determinístico
Todos os autômatos indicados em outras alternativas são equivalentes ao AFN dado
d(A, a) = C, d(A, b) = B, d(B, a) = C, d(B, b) = B, d(C, a) = D, d(C, b) = B, d(D, a) = D, d(D, b) = D
d(A, a) = C, d(A, b) = B, d(B, a) = C, d(B, b) = D, d(C, a) = D, d(C, b) = B, d(D, a) = D, d(D, b) = D
d(A, a) = C, d(A, b) = B, d(B, a) = C, d(B, b) = D, d(C, a) = D, d(C, b) = B, d(D, a) = C, d(D, b) = D
Respostas
Ed 
há 2 anos
A resposta correta é: "É impossível converter esse autômato finito não determinístico em um autômato finito determinístico".
Crie sua conta grátis para liberar essa resposta. 🤩
Já tem uma conta?
Ao continuar, você aceita os Termos de Uso e Política de Privacidade
Ainda com dúvidas?
Envie uma pergunta e tenha sua dúvida de estudo respondida!
Essa pergunta também está no material:
Mais perguntas desse material
Marque a alternativa que contém uma entrada inválida para o Autômato apresentado na figura abaixo:
11111
1000111
01010101
000000
10111
Sobre as linguagens regulares, considere as afirmativas a seguir.
I. As linguagens regulares formam a classe de linguagens mais simples, dentro da hierarquia de Chomsky.
II. As linguagens regulares podem ser expressas por um autômato finito.
III. Se A e B são linguagens regulares, então A ∩ B também é.
IV. Seja B = {ba, na}. Pode-se dizer que B* = {ε, ba, na, ab, an, baba, bana, naba, anab, nana, aban, bababa, babana, banaba, banana, nababa, nabana, nanaba, nanana, abanba, babababa, ... }.
Assinale a alternativa correta
I. As linguagens regulares formam a classe de linguagens mais simples, dentro da hierarquia de Chomsky.
II. As linguagens regulares podem ser expressas por um autômato finito.
III. Se A e B são linguagens regulares, então A ∩ B também é.
IV. Seja B = {ba, na}. Pode-se dizer que B* = {ε, ba, na, ab, an, baba, bana, naba, anab, nana, aban, bababa, babana, banaba, banana, nababa, nabana, nanaba, nanana, abanba, babababa, ... }.
Somente as afirmativas I, II e III são corretas.
Somente as afirmativas III e IV são corretas.
Somente as afirmativas I e IV são corretas.
Somente as afirmativas II, III e IV são corretas.
Somente as afirmativas I e II são corretas.
Considerando o formato da quíntupla, abaixo descrita, de um Autômato finito determinista:
M = (S, Q, d, q0, F)
marque a alternativa que apresente o objetivo do elemento S.
Função programa ou função de transição do autômato.
Representa o conjunto de estados finais do autômato.
Conjunto finito de símbolos de entrada para o autômato.
Conjunto finito de estados possíveis do autômato.
Representa o estado inicial do autômato.
A partir da Máquina de Turing abaixo, indica a letra que apresenta uma entrada válida:
1111
0110
1010
0111
0000
Assinale a afirmativa que contém apenas entradas válidas para o AFD abaixo:
011101, 101, 0100011
101, 0000111, 011101
010001, 101010, 0000111
0100011, 011101, 101010
101101101, 101010, 10101010
101, 0000111, 011101
010001, 101010, 0000111
0100011, 011101, 101010
101101101, 101010, 10101010
011101, 101, 0100011
Considerando a autômato finito determinista abaixo, marque a alternativa que representa o conjunto de dados de entrada que será aceito.
aaa
bbb
aabbbbbb
abb
bbaa
Mais conteúdos dessa disciplina
Ling Formais e Autômatos_Teste_ AO2- Videoaula 8 - Gramáticas
- SIMULADO 2
- Computabilidade e a máquina de
- Conceitos básicos de autômatos e
- Linguagens livres de contexto
- Classificação de Fenômenos
- Linguagens regulares
- Mapa Mental - Expressões Regulares
- Trabalho LFA 2025 1
- Algoritmo guloso
- (POSCOMP/2016) O automato finito exposto abaixo representa qual expressão regular? d b a C A ab^ * (da^ * + cb )^ * B a^ * b(d^ * + cb ) C (bb + d)...
- O problema da parada para máquinas de Turing, ou simplesmente problema da parada, pode ser assim descrito: determinar, para qualquer máquina de Tur...
- Em Braille, os sinais de abre e fecha parênteses são grafados da seguinte forma: Questão 2Resposta a. Pontos 1 2 3 4; 1 4 5 6. b. Pontos 1 2 3 5 6; 2
- Em Braille, os sinais de abre e fecha parênteses são grafados da seguinte forma: Questão 2Resposta a. Pontos 1 2 3 4; 1 4 5 6. b. Pontos 1 2 3 5 6; 2
- X Hb Fazer teste: QUESTIONÁRIO UN X + ht/webaps/assesment/take/launch.jsp?ourse_assesment_id=_1848023_18course_id=_418828_18content_id=4674001 tado...
- Assinale a única alternativa que contém a disposição correta da esquerda para a direita, em ordem crescente, dos tipos de gramática que, segundo a ...
- Considerando a hierarquia de Chomsky, leia as seguintes afirmativas:
Assinale a alternativa correta.
I. A hierarquia de Chomsky define quatro class...
- Considere a seguinte L(G) = (V, T, P, S), em que V = {0, 1, S}, T = {0, 1, λ} e P: S → OS1 e S → λ. Assinale a alternativa que contém somente cadei...
- Os símbolos são utilizados para construir __________, que são formadas pela __________ de símbolos. Um _________ é um conjunto finito e não vazio d...
- Palíndromos são cadeias que, lidas da esquerda para a direita ou da direita para a esquerda, têm a mesma sequência de símbolos e podem ser definida...
- Considere o conjunto A com 3 elementos; o B, com 4; e o C, com 5. Nesse caso, verificamos que:
A
tem, no máximo, 2 elementos.
tem, no máximo, 5 ele...
- Sabendo que o conjunto A = {0, 1, 3, 4, 5, 7} e A – B = {1, 3, 5, 7}, então o conjunto B é:
A
{0, 1, 4, 5}
{0, 1, 4, 5, 7}
{0, 4}
{0, 1, 5}
{}
- Uma árvore é um grafo: Simples, Acíclico (não possui ciclos), Conexo (existe caminho entre quaisquer dois de seus vértices).
Quais são as caracterí...
- Padrões de Projeto de Software 160 Questões COMPLETAS
- exercicios sistemas de tecnologias aplicadas a gestão publica 06