POSCOMP 2019: Questão 39 Resolvida (Linguagens Formais e Autômatos)

Por
| 

Logotipo do POSCOMP 2019

Questão

Seja $M$ uma máquina de Turing sobre alfabeto $\Sigma$. Denotamos por $\operatorname{ACEITA}(M)$ o conjunto de palavras aceitas por $M$. Uma linguagem $L \subseteq \Sigma^{*}$ é denominada Turing-reconhecível quando existe uma Máquina de Turing $M$ tal que $L = \operatorname{ACEITA}(M)$. Usaremos $\operatorname{TR}(L)$ para denotar que a linguagem $L$ é Turing-reconhecível. Nesse sentido, analise as seguintes afirmações sobre duas linguagens $L1$ e $L2$ sobre o alfabeto $\Sigma$:

  1. Se $\operatorname{TR}(L1)$ e $\operatorname{TR}(L2)$, então $\operatorname{TR}(L1 \cup L2)$.
  2. Se $\operatorname{TR}(L1)$, então $\operatorname{TR}(\Sigma^{*} \backslash L1)$.
  3. Se $\operatorname{TR}(L1)$ e $\operatorname{TR}(L2)$, então $\operatorname{TR}(L1 \cap L2)$.

Quais estão corretas?

  • (A) Apenas I.
  • (B) Apenas II.
  • (C) Apenas I e III.
  • (D) Apenas II e III.
  • (E) I, II e III.

Resolução

Se duas linguagens $L1$ e $L1$ são Turing reconhecíveis, ou seja, são recursivamente enumeráveis, então a união ($L1\cup L2$) e a intersecção ($L1\cap L2$) dessas linguagens também são recursivamente enumeráveis, ou seja, são Turing reconhecíveis. Portanto, as afirmações I e III estão corretas.

A afirmação II, por sua vez, está incorreta. Se uma linguagem é recursivamente enumerável, então não temos como afirmar que o seu complemento $\Sigma^{*}\backslash L1$ também é recursivamente enumerável. Isto é, ele pode ou não ser Turing reconhecível.

Portanto, a alternativa correta é a C.

Mais questões

Se você deseja mais questões resolvidas do POSCOMP 2019, acesse a tag Questões do POSCOMP 2019.

Agora, se você procura questões, gabaritos e caderno de questões de outras edições, então acesse a página POSCOMP.

Resolverei as questões conforme o tempo permitir e de acordo com os meus conhecimentos. Como eu não sei resolver todas as questões, recomendo que você consulte também o gabarito oficial do exame.

Referências

COUTINHO, S. C. Autômatos e Linguagens Formais. Rio de Janeiro: UFRJ, 2007. Acesso em 22 de março de 2020.

Obrigado pela leitura! Se você puder, considere apoiar financeiramente o Blog Cyberini. Qualquer valor doado contribui muito para a difusão do conhecimento.

Doar com PagSeguroDoar com PayPal


Siga o blog

Redes sociais: Facebook, Twitter, YouTube, Pinterest, Instagram, Telegram

Receba notificações de novas postagens e novidades do blog por e-mail.

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário