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

Por
|   

Nesta postagem, apresento algumas questões resolvidas do POSCOMP dos anos 2004, 2005, 2007 e 2008 sobre Linguagens Formais e Autômatos.

POSCOMP linguagens formais de 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

SAB|CDAa|ϵBb|fCc|gDh|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.

Diagrama da Hierarquia de Chomsky para Gramáticas
Hierarquia de Chomsky (Clique aqui para ampliar)

POSCOMP 2007

A questão a seguir é do ano 2007.

Questão 26

Seja a linguagem formal L={anb2nc,n0}. Analise as seguintes assertivas.

  • I. L é uma linguagem livre de contexto.
  • II. A gramática G=({S,X},{a,b,c},{SXc,XaXbb|ϵ},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 XaXbb|ϵ 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.

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