Linguagens formais e automatos

954S - LINGUAGENS FORMAIS E AUTÔMATOS

01) 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?

Resposta: B: 8

Justificativa: 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.

02) 1 - Considere-se o seguinte alfabeto:

A = { *, &, ?, ! }

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

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".

03) Assinale a alternativa correta:

Resposta: C: A Linguagem gerada por uma gramática é um conjunto que pode se apresentar com um número infinito de elementos.

Justificativa: Uma linguagem formal é um conjunto, finito ou infinito, de cadeias de comprimento finito, formadas pela concatenação de elementos de um alfabeto finito e não-vazio. Além das operações previamente definidas para conjuntos, como união, diferença, intersecção etc., outras operações, tais como a concatenação e os fechamentos, também são fundamentais para a definição e o estudo das linguagens formais.

04) Assinale a alternativa correta:

Resposta: D: Uma Linguagem Formal é um conjunto de palavras sobre um alfabeto.

Justificativa: Uma linguagem formal é um conjunto, finito ou infinito, de cadeias de comprimento finito, formadas pela concatenação de elementos de um alfabeto finito e não-vazio. Além das operações previamente definidas para conjuntos, como união, diferença, intersecção etc., outras operações, tais como a concatenação e os fechamentos, também são fundamentais para a definição e o estudo das linguagens formais.

05) Assinale a alternativa incorreta:

Resposta: B: Se um alfabeto A, A = {a, b}, então o conjunto Fechamento Recursivo é finito.

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

06) 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:

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.

07) Assinale a alternativa incorreta:

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

Justificativa: 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.

08) Assinale a alternativa correta:

Resposta: D: 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.

Justificativa: O automato construído usando o algoritmo de minimização apresentado é um automato finito deterministico com menor numero de estados que aceitam a linguagem

09) Assinale qual a alternativa que não diz respeito à minimização de um autômato finito:

Resposta: C: A função programa g deve ser tal que especifique duas transições que apresentem o mesmo estado origem, consomem o mesmo símbolo e apresentam estados destino distintos.

Justificativa: A máquina de estados de um autômato finito, também denominada controle finito, é definida pelo conjunto de estados Q e pela função de transição δ, que associa pares ordenados do tipo (estado corrente, entrada corrente) com um novo estado a ser assumido pelo autômato quando da aplicação da transição.

10) 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:

Resposta: D: