Nesta postagem, apresento algumas questões resolvidas do POSCOMP dos anos 2009, 2012, 2013, 2015 e 2016 sobre Linguagens Formais e Autômatos.
Se as fórmulas matemáticas não aparecerem ou ficarem estranhas, recarregue a página. Se o problema persistir, por favor, deixe um comentário para que eu possa averiguar o problema ou preencha o formulário de contato.
Leia também: Aplicativos para Estudar para o POSCOMP
POSCOMP 2009
As questões a seguir são do ano 2009.
Questão 45
Considere o autômato finito não-determinístico a seguir, sendo A o estado inicial e D o único estado de aceitação.
Que autômato finito determinístico com d como sua função de transição de estado aceita a mesma linguagem?
- (A)
Estado Inicial A, estados de aceitação C e D
d(A, b) = B
d(B, a) = C
d(C, a) = D - (B)
Estado Inicial A, estado de aceitação C
d(A, b) = B
d(B, a) = C
d(C, a) = C - (C)
Estado Inicial A, estado de aceitação D
d(A, b) = B
d(B, a) = D
d(B, b) = C
d(C, a) = D - (D) Todas as respostas acima estão corretas.
- (E) É impossível converter esse autômato finito não determinístico em um autômato finito determinístico.
Resolução
Primeiramente, observe que o autômato reconhece apenas duas cadeias, que formam uma linguagem finita: ba e baa. Isso elimina a alternativa B, pois a transição $d(C, a)=C$ gera um laço, portanto, a linguagem reconhecida pelo autômato em B é infinita.
Uma vez que B é falsa, então a alternativa D é automaticamente falsa.
A alternativa E também é falsa, pois qualquer AFND pode ser convertido em um AFD, pois as duas classes de autômatos são equivalentes.
O autômato em C reconhece a linguagem L = {ba, bba}, que é diferente da linguagem do autômato da questão. Logo, a alternativa C está errada.
A única alternativa correta é a A. O autômato de A é representado a seguir.
Questão 56
Qual é a linguagem da gramática com as seguintes regras de produção
$$\begin{align*}S&\rightarrow ASb\,|\,c\\A&\rightarrow a\end{align*}$$
- (A) $\{a^ncb\,|\,n\in\mathbb{N}\}$
- (B) $\{acb^n\,|\,n\in\mathbb{N}\}$
- (C) $\{a^nc^nb\,|\,n\in\mathbb{N}\}$
- (D) $\{a^ncb^n\,|\,n\in\mathbb{N}\}$
- (E) Nenhuma das respostas anteriores
Resolução
A gramática pode ser simplificada
$$S\rightarrow aSb|c$$
Para cada a à esquerda, teremos um b à direita e, no meio, temos um c:
$$L=\{c,acb,aacbb,aaacbbb,\ldots\}$$
Portanto, a alternativa correta é a D.
POSCOMP 2012
A questão a seguir é de 2012.
Questão 41
Seja um Autômato Finito Não Determinístico (AFN) com 6 estados. Aplicando-se o algoritmo de conversão de um AFN para um Autômato Finito Determinístico (AFD), em quantos estados, no máximo, resultaria o AFD considerando-se os estados inúteis?
- (A) 12
- (B) 36
- (C) 64
- (D) 1024
- (E) 46656
Resolução
O cálculo é simples. Basta calcular 2 elevado ao número de estados do AFN:
$$2^6=64\text{ estados}$$
Portanto, a alternativa C é a correta.
POSCOMP 2013
A questão a seguir é de 2013.
Questão 41
Se o estado inicial for também estado final em um autômato finito, então esse autômato
- (A) não aceita a cadeia vazia.
- (B) não tem outros estados finais.
- (C) é determinístico.
- (D) aceita a cadeia vazia.
- (E) é não determinístico.
Resolução
A questão é fácil. Quando o estado inicial também é final num AF, então ele aceita a cadeia vazia. Logo, a opção certa é a D.
POSCOMP 2015
As questões a seguir são do ano 2015.
Questão 39
A gramática $G = (\{S, A, B\}, \{0, 1\}, P, S)$, onde $P$ é dado pelas regras de produção
$$\begin{align*}S&\rightarrow 0AB\,|\,1BA\\A&\rightarrow 0AS\,|\,1A\,|\,\varepsilon\\B&\rightarrow 0B\,|\,1BS\,|\,\varepsilon\end{align*}$$
gera uma linguagem que
- (A) pertence à classe Regular.
- (B) contém a cadeia vazia $\varepsilon$
- (C) pode ser aceita por um autômato com pilha.
- (D) pode ser denotada por uma expressão regular.
- (E) é igual ao conjunto de cadeias {x ∈ {0, 1}* | x tem quantidade igual de zero (0) e de um (1)}}
Resolução
$G$ é uma gramática livre de contexto que, consequentemente, gera uma linguagem livre de contexto. Toda linguagem livre de contexto pode ser reconhecida por um autômato com pilha.
Portanto, a alternativa correta é a C.
Questão 40
Considerando as linguagens $L =\{0^n1^n2^i\,|\,n \geq 0\,e\,i\geq 0\}$ e $M =\{0^i1^n2^n\,|\,n \geq 0\,e\,i\geq 0\}$, pode-se afirmar que
- (A) a linguagem $L\cup M$ pode ser gerada por uma gramática livre de contexto.
- (B) a linguagem M pode ser gerada por uma gramática regular.
- (C) a linguagem L pode ser aceita por um autômato finito determinístico.
- (D) a linguagem $L\cap M$ pertence à classe das linguagens livres de contexto.
- (E) a linguagem M pode ser denotada por uma expressão regular.
Resolução
As duas linguagens são livres de contexto, por causa da "simetria" relacionada à variável $n$. Assim, essas linguagens só podem ser geradas por gramáticas livres de contexto. Só isso já descarta as alternativas B, C e E.
A alternativa D é falsa, pois a linguagem $L\cap M$ é representada por $0^n1^n2^n$, que não pode ser gerada por uma gramática livre de contexto. Portanto, $L\cap M$ não é livre de contexto. Na prática, essa linguagem é sensível ao contexto.
A alternativa A está correta. Uma gramática livre de contexto capaz de gerar $L\cup M$ é representada a seguir
$$G=\left(\{S,A,B,C,D\},\{0,1\},P,S\right)$$
$$\begin{align*}S&\rightarrow AB|CD\\A&\rightarrow 0A1|\lambda\\B&\rightarrow 2B|\lambda\\C&\rightarrow 0C|\lambda\\D&\rightarrow 1D2|\lambda\end{align*}$$
POSCOMP 2016
A questão a seguir é de 2016.
Questão 39
O grafo rotulado G(r), exposto abaixo, representa qual expressão regular?
- (A) $r=ab^{*}(da^{*}+cb)^{*}$
- (B) $r=a^{*}b(d^{*}+cb)$
- (C) $r=(bb+d)^{*}(aa+c)^{*}$
- (D) $r=a^{*}b(c+da^{*}b)^{*}$
- (E) $r=a^{*}c^{*}(b+d)^{*}$
Resolução
Partindo do estado inicial, podemos gerar 0 (zero) ou mais a's e, em seguida, gerar um b, mudando para o estado final. Ou seja, a expressão regular deve iniciar com $a^{*}b$. Isso elimina as alternativas A, C e E.
Depois, podemos simplesmente parar no estado final ou gerar combinações de c's ou $da^{*}b$. Isto é, $\left(c|da^{*}b\right)^{*}$. Combinando as expressões, obtemos a expressão regular completa, que é $a^{*}b\left(c|da^{*}b\right)^{*}$. Portanto, a alternativa correta é a D.
Observação: o operador "+" é o operador de união "|". A notação "+" para esse operador é pouco comum (os elaboradores do POSCOMP costumam utilizá-la nas provas).
Postagens Relacionadas
Questões do POSCOMP sobre Complexidade de Algoritmos #01
Questões do POSCOMP sobre Linguagens Formais e Autômatos #03
Acesse a tag POSCOMP do blog para ver mais postagens sobre a prova.
Nenhum comentário:
Postar um comentário