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

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:

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

Nesse sentido, considere as seguintes afirmações:

$L1$ é uma linguagem regular.
$L2$ é uma linguagem livre de contexto.
$\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.