Grátis: Considere os seguintes problemas de decisão: P1: Uma determinada máquina de estado finito aceita uma determinada cadeia. P2: Uma determinada gramát... – Questões Respondidas

Teoria da Computação

Outros

Considere os seguintes problemas de decisão: P1: Uma determinada máquina de estado finito aceita uma determinada cadeia. P2: Uma determinada gramática livre de contexto gera um número infinito de cadeias. Qual das seguintes afirmações é verdadeira?
A) Ambos P1 e P2 são decidíveis.
B) Nem P1 nem P2 são decidíveis.
C) Apenas P1 é decidível.
D) Apenas P2 é decidível.
E) P1 e P2 não são problemas de decisão.

Progresso com Exercícios

há 5 meses

Progresso com Exercícios

há 5 meses

estacio saladeavaliacoes com br_prova_673ce34d42bc354409b0c865_

estacio saladeavaliacoes com br_prova_673ce34d42bc354409b0c865_

ESTÁCIO

Respostas

Ed

há 5 meses

Vamos analisar os problemas de decisão apresentados: P1: "Uma determinada máquina de estado finito aceita uma determinada cadeia." Este problema é decidível. Podemos construir um algoritmo que simula a máquina de estado finito com a cadeia de entrada e verifica se ela é aceita ou não. P2: "Uma determinada gramática livre de contexto gera um número infinito de cadeias." Este problema também é decidível. Podemos verificar se a gramática gera um número infinito de cadeias analisando suas produções e a estrutura da gramática. Agora, analisando as alternativas: A) Ambos P1 e P2 são decidíveis. - Correto, pois ambos os problemas são decidíveis. B) Nem P1 nem P2 são decidíveis. - Incorreto, pois ambos são decidíveis. C) Apenas P1 é decidível. - Incorreto, pois P2 também é decidível. D) Apenas P2 é decidível. - Incorreto, pois P1 também é decidível. E) P1 e P2 não são problemas de decisão. - Incorreto, pois ambos são problemas de decisão. Portanto, a alternativa correta é: A) Ambos P1 e P2 são decidíveis.

Essa resposta te ajudou?

0

0

left-side-bubbles-background

right-side-bubbles-background

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:

estacio saladeavaliacoes com br_prova_673ce34d42bc354409b0c865_

estacio saladeavaliacoes com br_prova_673ce34d42bc354409b0c865_

ESTÁCIO

Mais perguntas desse material

Seja $G=(V, T, P, E)$, onde $V=$ $\{+, ,(), ext{id}, ext{T}, ext{F}, ext{E}\}$, $ ext{T}=\{+, ,(, ), ext{id}\}$ e $ ext{P}$: 1. $E \rightarrow E + T$ 4. $T \rightarrow F$ 2. $E \rightarrow T$ 5. $F \rightarrow (E)$ 3. $T \rightarrow T * F$ 6. $F \rightarrow ext{id}$ Os símbolos $E, T, F$ são abreviaturas para expressão, termo e fator, respectivamente e $ ext{id}$ é um identificador válido dessa linguagem. Assinale a alternativa que tem uma derivação correta para a expressão $ ext{id} + (\text{id} * \text{id})$:
A) $T \Rightarrow 4 F \Rightarrow 5(E) \Rightarrow 1(E+ T) \Rightarrow 3 (E + TF) \Rightarrow 4 (F + FF) \Rightarrow 6 (\text{id} + \text{id} \text{id})$.
B) $E \Rightarrow 1 E+T \Rightarrow 3 E+T F \Rightarrow 5 E+T (E) \Rightarrow 1 E + T (E+T) \Rightarrow 2 T * (T+T) \Rightarrow 4 F (F+F) \Rightarrow 6 \text{id} (\text{id}+ \text{id})$.
C) $E \Rightarrow 1 E+T \Rightarrow 2 T+T \Rightarrow 4 T+F \Rightarrow 5 T+(E) \Rightarrow 2 T+(T) \Rightarrow 3 T+(T * F) \Rightarrow 4 F+(F * F) \Rightarrow 6 \text{id}+(\text{id} * \text{id})$.

Considere o autômato finito mostrado na figura abaixo (os círculos concêntricos representam estado final) e assinale a afirmativa correta.
A) A palavra vazia não é reconhecida pelo autômato.
B) A palavra 01010 não é reconhecida pelo autômato.
C) A palavra 10101 é reconhecida pelo autômato.
D) A palavra 101 é reconhecida pelo autômato.
E) A palavra vazia é reconhecida pelo autômato.

Se $\sum=\{1\}$, então $\sum^{}-\sum^{+}$é
A) $1+$
B) $\{1\}$
C) $\{\lambda, 1,11 \underline{i} \ldots\}$
D) $\lambda$
E) $1 $

Acerca das características dos problemas decidíveis e indecidíveis e das diferentes linguagens da hierarquia de Chomsky e suas respectivas máquinas reconhecedoras, analise as afirmações a seguir e assinale a falsa.
A) O problema da parada de uma máquina de Turing é indecidível.
B) É possível construir uma máquina de Turing que aceita qualquer cadeia de comprimento par.
C) Dadas duas gramáticas livres de contexto G1 e G2, é indecidível se L(G1) = L(G2).
D) Seja G1 qualquer gramática irrestrita e G2 seja qualquer gramática regular, então $L(G_{1}) \cap L(G_{2})= \varnothing$, é indecidível.
E) Nenhum procedimento computacional é considerado um algoritmo a menos que seja representado pela máquina de Turing.

A teoria dos autômatos é o estudo de máquinas $\qquad$ e os problemas computacionais relacionados a essas máquinas, chamadas de $\qquad$ . São aplicados em diferentes áreas da ciência da computação e da $\qquad$ . Sua aplicação mais tradicional é encontrada na construção de Assinale a alternativa que preenche, correta e respectivamente, as lacunas do trecho acima.
A) de estado finito computadores - TI computadores
B) determinísticas computadores matemática - circuitos elétricos
C) abstratas - autômatos - engenharia compiladores
D) automáticas compiladores engenharia corretores ortográficos
E) abstratas compiladores engenharia computadores

Qual é a linguagem da gramática com as seguintes regras de produção: $S \rightarrow ASb \mid c$, $A \rightarrow a$
A) $\{a^{n} c b \mid n \in \mathbb{N}\}$
B) $\{a c b^{n} \mid n \in \mathbb{N}\}$
C) $\{a^{n} c^{n} b \mid n \in \mathbb{N}\}$
D) $\{a^{n} c b^{n} \mid n \in \mathbb{N}\}$
E) $\{a c^{n} b \mid n \in \mathbb{N}\}$

A linguagem gerada pelo GLC é chamada de linguagem livre de contexto (LLC). Acerca de suas características, a linguagem livre de contexto não é fechada em relação a:
A) União.
B) Concatenação.
C) Complementação.
D) Fechamento de Kleene.
E) Divisão.