Questões do POSCOMP sobre Linguagens Formais e Autômatos #04

Por
|   

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.

Autômato da questão 45 do POSCOMP 2009
Autômato da questão 45 do POSCOMP 2009

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.

Autômato da solução da questão 45 do POSCOMP 2009
Autômato da alternativa A

Questão 56

Qual é a linguagem da gramática com as seguintes regras de produção

SASb|cAa

  • (A) {ancb|nN}
  • (B) {acbn|nN}
  • (C) {ancnb|nN}
  • (D) {ancbn|nN}
  • (E) Nenhuma das respostas anteriores
Resolução

A gramática pode ser simplificada

SaSb|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

S0AB|1BAA0AS|1A|εB0B|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|n0ei0} e M={0i1n2n|n0ei0}, pode-se afirmar que

  • (A) a linguagem LM 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 LM 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 LM é representada por 0n1n2n, que não pode ser gerada por uma gramática livre de contexto. Portanto, LM 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 LM é representada a seguir

G=({S,A,B,C,D},{0,1},P,S)

SAB|CDA0A1|λB2B|λC0C|λD1D2|λ

POSCOMP 2016

A questão a seguir é de 2016.

Questão 39

O grafo rotulado G(r), exposto abaixo, representa qual expressão regular?

Autômato da questão 39 do POSCOMP 2016
Autômato/grafo da questão 39 do POSCOMP 2016
  • (A) r=ab(da+cb)
  • (B) r=ab(d+cb)
  • (C) r=(bb+d)(aa+c)
  • (D) r=ab(c+dab)
  • (E) r=ac(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 ab. Isso elimina as alternativas A, C e E.

Depois, podemos simplesmente parar no estado final ou gerar combinações de c's ou dab. Isto é, (c|dab). Combinando as expressões, obtemos a expressão regular completa, que é ab(c|dab). 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 do blog para ver mais postagens sobre a prova.

Sugestões de livros para estudantes de computação na Amazon (patrocinado): Lista de Livros

Obrigado pela leitura! Se você puder, considere apoiar financeiramente o Blog Cyberini, Chave Pix: cyberpix9@gmail.com

Doar com PayPal

Siga o blog

Redes sociais: Facebook, Twitter, YouTube, Pinterest, Instagram, Telegram

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário

Este site usa cookies para fornecer serviços, analisar o tráfego e exibir publicidade personalizada, conforme a nossa política de privacidade. Seus dados, como IP e user agent, são compartilhados com nossos parceiros (como o Google). Saiba Mais

RecusarAceitar