Logo Passei Direto
Buscar

Teoria da Computação

Outros
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.
User badge image
Progresso com Exercícios

há 5 meses

User badge image
Progresso com Exercícios

há 5 meses

estacio saladeavaliacoes com br_prova_673ce34d42bc354409b0c865_
10 pág.

estacio saladeavaliacoes com br_prova_673ce34d42bc354409b0c865_

ESTÁCIO

Respostas

User badge image

Ed Verified user icon

há 5 meses

Vamos analisar cada uma das afirmações para identificar a falsa: A) O problema da parada de uma máquina de Turing é indecidível. - Esta afirmação é verdadeira. O problema da parada é um exemplo clássico de um problema indecidível. B) É possível construir uma máquina de Turing que aceita qualquer cadeia de comprimento par. - Esta afirmação é verdadeira. Uma máquina de Turing pode ser construída para aceitar cadeias de comprimento par, simplesmente verificando se o número de símbolos é par. C) Dadas duas gramáticas livres de contexto G1 e G2, é indecidível se L(G1) = L(G2). - Esta afirmação é verdadeira. A igualdade de linguagens geradas por gramáticas livres de contexto é um problema indecidível. 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. - Esta afirmação é falsa. Na verdade, é possível que a interseção de uma gramática irrestrita e uma gramática regular não seja vazia, e a questão de se a interseção é vazia é decidível. E) Nenhum procedimento computacional é considerado um algoritmo a menos que seja representado pela máquina de Turing. - Esta afirmação é um pouco confusa, mas em geral, algoritmos podem ser representados de várias formas, não apenas por máquinas de Turing. Portanto, essa afirmação pode ser considerada falsa em um contexto mais amplo. A afirmação falsa, que se destaca claramente, é a D. Portanto, a resposta correta é a alternativa D.

Essa resposta te ajudou?

0
Dislike0
left-side-bubbles-backgroundright-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_
10 pág.

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 + T*F) \Rightarrow 4 (F + F*F) \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 *$

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.

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.

Mais conteúdos dessa disciplina