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
S→ASb|cA→a
- (A) {ancb|n∈N}
- (B) {acbn|n∈N}
- (C) {ancnb|n∈N}
- (D) {ancbn|n∈N}
- (E) Nenhuma das respostas anteriores
Resolução
A gramática pode ser simplificada
S→aSb|c
Para cada a à esquerda, teremos um b à direita e, no meio, temos um c:
L={c,acb,aacbb,aaacbbb,…}
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:
26=64 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
S→0AB|1BAA→0AS|1A|εB→0B|1BS|ε
gera uma linguagem que
- (A) pertence à classe Regular.
- (B) contém a cadeia vazia ε
- (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={0n1n2i|n≥0ei≥0} e M={0i1n2n|n≥0ei≥0}, pode-se afirmar que
- (A) a linguagem L∪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∩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∩M é representada por 0n1n2n, que não pode ser gerada por uma gramática livre de contexto. Portanto, L∩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∪M é representada a seguir
G=({S,A,B,C,D},{0,1},P,S)
S→AB|CDA→0A1|λB→2B|λC→0C|λD→1D2|λ
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 é, (c|da∗b)∗. Combinando as expressões, obtemos a expressão regular completa, que é a∗b(c|da∗b)∗. 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