Linguagens Formais e Automatos

1. Dispositivos que processam Linguagens Regulares, muitas vezes, após seu projeto inicial devem ser alterados. Os algoritmos disponíveis , partem de uma premissa inicial que se o projeto inicial apresenta um conjunto Q de estados, o dispositivo final, apresentará um conjunto de estados representados pelos elementos do conjunto 2Q ; Se um dispositivo foi projetado com 3 estados, qual o maior número de estados que o dispositivo final poderá apresentar?

1. 6
2. 8
3. 27
4. 9
5. 3

Resposta:B) 8

Uma linguagem regular é uma linguagem formal que pode ser expressa usando expressões regulares, ou seja, uma linguagem produzida utilizando as operações de concatenação, união e fecho de Kleene sobre os elementos de um alfabeto. De acordo com a hierarquia de Chomsky, linguagens regulares são aquelas geradas por gramática regulares.

As linguagens regulares são utilizadas para descrever dispositivos que realizam computações simples, como os autômatos finitos, pois representam a linguagem mais elementar classificada pela hierarquia de Chomsky que não requer memória para ser reconhecida.

1. Considere-se o seguinte alfabeto:

A = { *, &, ?, ! }

Qual a alternativa que apresenta uma palavra não definida sobre o alfabeto:

1. Asterisco
2. ***
3. ???
4. ?*!
5. !

Resposta: A: asterisco.

Justificativa: Uma linguagem formal de L sobre um alfabeto Σ é um subconjunto de Σ *, isto é, um conjunto de palavras sobre um alfabeto. Por vezes, os conjuntos de palavras são agrupados em expressões, que as regras e as constantes podem ser formuladas para a criação de "expressões bem formadas".

1. O estudo das Linguagens Livres de Contexto, apresenta ampla aplicação no projeto e implementação do Analisador Sintático, módulo funcional de um compilador. Assim sendo, faz-se necessário que no projeto do compilador, uma gramática livre de contexto não apresente qual característica?

1. Conjunto de símbolos não terminais finito;
2. Conjunto de símbolos terminais finito;
3. Conjunto de produções finito;
4. Apenas uma raiz, ou símbolo inicial;
5. Ambiguidade;

Resposta: E: Ambiguidade;

Uma gramática livre de contexto é ambígua quando existir pelo menos uma cadeia, pertencente à linguagem por ela gerada, que possua mais de uma seqüência distinta de derivações, feitas exclusivamente através de substituições de não-terminais mais à esquerda ou mais à direita.

1. Assinale a alternativa incorreta:

1. A palavra acbcb é uma palavra sobre o alfabeto A = {a, b, c}.
2. Se um alfabeto A, A = {a, b}, então o conjunto Fechamento Recursivo é finito.
3. Qualquer prefixoo ou sufixo de uma palavra é uma sub-palavra.
4. A palavra vazia   é prefixo da palavra abc.
5. |abcbe| = 5 (lê-se, comprimento da cadeia).

Resposta: B)

 O alfabeto A, A = {a, b} é um fechamento recursivo e transitivo.

1. Considere as seguintes afirmações:

I – A Classe dos Autômatos Finitos Determinísticos é equivalente à Classe dos Autômatos Finitos Não-Determinísticos.

II – Para uma particular Linguagem Regular, pode não existir uma gramática geradora da mesma.

III – Uma Linguagem Regular é sempre finita.

IV – Um Autômato Finito a ser minimizado deve ser determinístico;

 São verdadeiras as afirmações:

1.  I, II, III e IV;
2.  I, II e IV;
3.  I, II e III;
4.  Apenas I e IV;
5.  Apenas I e III;

Resposta: D: Apenas I e IV;

Justificativa: Seja o autômato determinístico ou não-determinístico, a linguagem por ele aceita ou definida corresponde ao conjunto de todas as cadeias que ele aceita.

1. Assinale a alternativa incorreta:

1. A Classe dos Autômatos Fintos Determinísticos é equivalente à Classe dos Autômatos Finitos Não-Determinísticos, ou seja a partir de um Autômato Finito Não-Determinístico é possível construir um autômato finito determinístico e vice-versa.
2. Um autômato finito que apresenta transições em vazio é um autômato finito não-determinísticos.
3. Autômatos Finitos são dispositivos geradores de Linguagens Regulares.
4. Um autômato finito para ser minimizado deve ser determinístico.
5. Um autômato mínimo é um autômato que apresenta o menor número de estados. O Autômato mínimo para uma linguagem é único a menos de isomorfismo.

Resposta: C: Autômatos Finitos são dispositivos geradores de Linguagens Regulares.

Autômatos finitos podem ser projetados para reconhecer uma classe de linguagens chamadas de linguagens regulares. Gramaticas regulares são dispositivos geradores para linguagens regulares. Os tokens de uma linguagem de programação formam uma linguagem regular, e um analisador léxico é um automato finito.

1. As Linguagens Regulares apresentam como dispositivo aceitador de cadeias corretas os autômatos finitos e são geradas por Gramáticas Regulares. Linguagens Regulares também podem ser definidas por expressões regulares. Assinale a alternativa que apresenta uma característica das Linguagens Livres de Contexto que não pode ser processada pelos formalismos ´associados às Linguagens Regulares:

1. Ocorrências opcionais de símbolos  do alfabeto na  Linguagem;
2. Ocorrências de símbolos obrigatórios na Linguagem;
3. Não-determinismos;
4. Linguagem com alfabeto finito;
5. Aninhamentos sintáticos;

Resposta: E: aninhamentos sintáticos;

Gramáticas livres de contexto permitem impor restrições adicionais àquelas que se podem construir em gramáticas regulares, podendo assim caracterizar subconjuntos das linguagens regulares que gozem da propriedade determinada pelos aninhamentos sintáticos;

...