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

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.