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 ϵ representa a sentença vazia
S→AB|CDA→a|ϵB→b|fC→c|gD→h|i
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 Σ e uma string w∈Σ, 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={anb2nc,n≥0}. Analise as seguintes assertivas.
- I. L é uma linguagem livre de contexto.
- II. A gramática G=({S,X},{a,b,c},{S→Xc,X→aXbb|ϵ},S) 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→aXbb|ϵ produz anb2n, 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