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

Por
| 

Logotipo do POSCOMP 2019

Questão

Considere $L1$ e $L2$ duas linguagens formais sobre o alfabeto $\Sigma=\{0,1\}$, descritas como segue:

$L1 = \{ww\, |\, w \in \Sigma^{*}\}$

$L2 = \{0^a1^b \, |\, a>0, b>0, b \text{ ímpar}\}$

Na descrição acima, justaposição significa concatenação de palavras e $\Sigma^{*}$ denota o conjunto de todas as palavras sobre o alfabeto $\Sigma$.

Seja $A1$ o autômato finito sobre alfabeto $\Sigma = \{0,1\}$ descrito pelo seguinte diagrama de transição de estados:

Autômato da Questão 41 do POSCOMP 2019

Denotemos por $\operatorname{ACEITA}(A1)$ o conjunto de palavras aceitas por $A1$.

Nesse sentido, considere as seguintes afirmações:

  1. $L1$ é uma linguagem regular.
  2. $L2$ é uma linguagem livre de contexto.
  3. $\operatorname{ACEITA}(A1) = \{ w\, |\, w \in \Sigma^{*}\text{ e }w\text{ possui um número ímpar de zeros}\}$.

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

A afirmação III está incorreta. A cadeia $1000$ possui um número ímpar de zeros, porém não é aceita pelo autômato, já que as cadeias aceitas por ele devem necessariamente começar com zero. Isso elimina as alternativas C, D e E.

A afirmação II está correta. A linguagem $L2$ é regular e, portanto, também livre de contexto segundo a Hierarquia de Chomsky, podendo ser expressa pela expressão regular $00^{*}1(11)^{*}$ e gerada pela gramática regular a seguir ($\varepsilon$ é a cadeia vazia):

$$\begin{align*}& S \rightarrow 0A\\& A \rightarrow 0A\, |\, 1B\\& B \rightarrow 11B\, |\, \varepsilon\end{align*}$$

Diagrama da Hierarquia de Chomsky para Gramáticas
Hierarquia de Chomsky

A afirmação I é falsa, pois a linguagem $L1$ não é regular e isso pode ser demonstrado via Lema do Bombardeamento para Linguagens Regulares [4].

Curiosamente, $L1$ também não é livre de contexto e isso é demonstrável através do Lema de Bombardeamento para Linguagens Livres de Contexto [1][2][3].

Em ambos os casos, consulte as referências, pois nelas você encontra as demonstrações específicas para a linguagem $L1$.

Enfim, a alternativa correta é a B.

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

Sugestões de livros para estudantes de computação na Amazon (patrocinado): Lista de Livros

Obrigado pela leitura! Se você puder, considere apoiar financeiramente o Blog Cyberini, Chave Pix: cyberpix9@gmail.com

Doar com PayPal

Siga o blog

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

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

2 comentários:

  1. Essa questão realmente esta correta?

    ResponderExcluir
    Respostas
    1. A questão ou a solução?

      A afirmação I é falsa, e pode ser provada via lema do bombardeamento (os links nas referências têm demonstrações específicas para linguagem da questão);

      II é verdadeiro, conforme expliquei na postagem.

      III é falso e eu expliquei utilizando a cadeia 1000 como contraexemplo. A cadeia 1000 pertence à Σ∗ e tem um número ímpar de zeros, porém não é aceita pelo autômato.

      Excluir