Nesta postagem, apresento algumas questões resolvidas do POSCOMP dos anos 2004, 2005, 2007 e 2008 sobre Linguagens Formais e Autômatos.
Para mais questões resolvidas, acesse a página POSCOMP.
POSCOMP 2004
A questão a seguir é do ano 2004.
Questão 62
Seja a seguinte linguagem, onde $\epsilon$ representa a sentença vazia
$$\begin{align*}S&\rightarrow AB\,|\,CD\\A&\rightarrow a\,|\,\epsilon\\B&\rightarrow b\,|\,f\\C&\rightarrow c\,|\,g\\D&\rightarrow h\,|\,i\end{align*}$$
Qual o conjunto de terminais que podem começar sentenças derivadas de $S$?
- (A) $\{a, c, g\}$
- (B) $\{a, b, f, c, g\}$
- (C) $\{a, b, f, c, g, h, i\}$
- (D) $\{a, c, g, h, i\}$
- (E) $\{a, b, f\}$
Resolução
Na prática, o enunciado solicita o conjunto FIRST de S.
Todos os terminais que iniciam sentenças produzidas pelos não terminais A e C fazem parte do conjunto: $\{a, c, g\}$. Como A produz a cadeia vazia, então devemos também incluir os não terminais que iniciam sentenças produzidas pelo não terminal B: $\{b, f\}$.
Unindo os conjuntos, temos: $\{a, b, c, f, g\}$. Portanto, a alternativa correta é a B.
POSCOMP 2005
A questão a seguir é do ano 2005.
Questão 28
Qual das seguintes afirmações é falsa?
- (A) Dada uma máquina de Turing M com alfabeto de entrada $\Sigma$ e uma string $w\in\Sigma$, não se sabe se a computação de M com entrada $w$ vai ou não parar.
- (B) O problema da parada é indecidível.
- (C) Não existe algoritmo que determina quando uma gramática livre de contexto arbitrária é ambígua.
- (D) Não existe autômato finito determinístico que reconheça alguma linguagem livre de contexto.
- (E) Um autômato com duas pilhas pode ser simulado por uma máquina de Turing.
Resolução
A única alternativa falsa é a D. Linguagens regulares são reconhecidas por autômatos finitos determinístico e, pela hierarquia de Chomsky, toda linguagem regular também é livre de contexto.
POSCOMP 2007
A questão a seguir é do ano 2007.
Questão 26
Seja a linguagem formal $L = \{a^nb^{2n}c,n\geq 0\}$. Analise as seguintes assertivas.
- I. $L$ é uma linguagem livre de contexto.
- II. A gramática $G=\left(\{S,X\},\{a,b,c\},\{S\rightarrow Xc, X\rightarrow aXbb|\epsilon\},S\right)$ gera a linguagem $L$.
- III. $L$ não pode ser reconhecida por um autômato com pilha.
A análise permite concluir que estão CORRETAS
- (A) apenas as assertivas I e II.
- (B) apenas as assertivas I e III.
- (C) apenas as assertivas II e III.
- (D) todas as assertivas.
- (E) nenhuma das assertivas.
Resolução
As afirmativas I e II estão corretas. A gramática G é livre de contexto e produz corretamente a linguagem L.
A produção $X\rightarrow aXbb|\epsilon$ produz $a^nb^{2n}$, isto é, para cada a à esquerda, teremos dois b's à direita. Essa "simetria" não pode ser expressa por uma gramática regular.
Uma vez que a gramática G é livre de contexto, então a linguagem L, produzida por G, é livre de contexto.
A afirmativa III está incorreta, pois como a linguagem L é livre de contexto, então ela é reconhecida por um autômato com pilha.
Portanto, a alternativa correta é a A.
POSCOMP 2008
As questões a seguir são do POSCOMP 2008.
Questão 30
Analise as seguintes afirmativas.
- I. Todo autômato finito não-determinístico pode ser simulado por um autômato finito determinístico.
- II. Todo autômato finito determinístico pode ser simulado por um autômato finito não-determinístico.
- III. Todo autômato finito não-determinístico pode ser simulado por um autômato de pilha determinístico.
- IV. Todo autômato de pilha determinístico pode ser simulado por um autômato finito não-determinístico.
- V. Todo autômato finito não-determinístico pode ser simulado por uma máquina de Turing determinística.
A análise permite concluir que estão CORRETAS
- (A) apenas as afirmativas I, II, III e IV.
- (B) apenas as afirmativas II, III e V.
- (C) apenas as afirmativas I, II, III e V.
- (D) apenas as afirmativas II e IV.
- (E) apenas as afirmativas I, II e IV.
Resolução
A única afirmativa falsa é a IV. Autômatos de pilha reconhecem linguagens livres de contexto, enquanto que autômatos finitos reconhecem linguagens regulares.
Portanto, é impossível simular um autômato de pilha utilizando um autômato finito, pois a classe de linguagens que esse último reconhece é hierarquicamente inferior.
Além disso, autômatos finitos não possuem memória auxiliar para simular a pilha.
Logo, a alternativa correta é a C.
Questão 42
Analise as seguintes igualdades de expressões regulares:
- I. $a^{*} = (a^{*})^{*}$
- II. $(a+b)^{*} = (b+a)^{*}$
- III. $a^{*}+b^{*} = (a+b)^{*}$
A análise permite concluir que
- (A) somente as igualdades I e II são verdadeiras.
- (B) somente a igualdade I é verdadeira.
- (C) somente as igualdades II e III são verdadeiras.
- (D) todas as igualdades são verdadeiras.
- (E) nenhuma das igualdades é verdadeira.
Resolução
Nas afirmativas II e III o operador "+" não é o fecho positivo e sim o operador de união. Podemos reescrever as afirmativas da seguinte forma:
- II. $(a|b)^{*}=(b|a)^{*}$
- III. $a^{*}|b^{*}=(a|b)^{*}$
A afirmativa I está correta (é trivial).
A afirmativa II também está correta (também é trivial, pois o operador de união "|" é comutativo).
A afirmativa III está errada. Enquanto a expressão regular à esquerda reconhece cadeias contendo apenas a's ou cadeias contendo apenas b's, a expressão regular à direita reconhece qualquer cadeia de a's e b's. Por exemplo, a cadeia aab é reconhecida por $(a|b)^{*}$, mas não é reconhecida por $a^{*}|b^{*}.$
Portanto, a alternativa correta é a A.
Nenhum comentário:
Postar um comentário