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.

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 2004

A questão a seguir é do ano 2004.

Questão 62

Seja a seguinte linguagem, onde $\epsilon$ representa a sentença vazia

$$\begin{align*}S&\rightarrow AB\,|\,CD\\A&\rightarrow a\,|\,\epsilon\\B&\rightarrow b\,|\,f\\C&\rightarrow c\,|\,g\\D&\rightarrow h\,|\,i\end{align*}$$

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 $\Sigma$ e uma string $w\in\Sigma$, 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 = \{a^nb^{2n}c,n\geq 0\}$. Analise as seguintes assertivas.

  • I. $L$ é uma linguagem livre de contexto.
  • II. A gramática $G=\left(\{S,X\},\{a,b,c\},\{S\rightarrow Xc, X\rightarrow aXbb|\epsilon\},S\right)$ 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\rightarrow aXbb|\epsilon$ produz $a^nb^{2n}$, 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.

Postagens Relacionadas

Questões do POSCOMP sobre Complexidade de Algoritmos #01

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

Acesse a tag do blog para ver mais postagens sobre a prova.

Siga o blog por e-mail

Receba notificações de novas postagens e novidades do blog por e-mail.

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