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*}$$
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
- [1] GeeksforGeeks Check if the language is Context Free or Not. Acesso em 27 de março de 2020.
- [2] StackOverflow. Is WW where W belongs to {a,b}* a context free language?. Acesso em 27 de março de 2020.
- [3] Pumping Lemma. Acesso em 27 de março de 2020.
- [4] PELLEGRINI, J. C. Linguagens Formais e Autômatos (Notas de aula). Acesso em 27 de março de 2020.
Essa questão realmente esta correta?
ResponderExcluirA questão ou a solução?
ExcluirA 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.