Linguagens Formais e Automatos

...

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

- Autômato finito deve ser determinístico;

- Não pode ter estados inacessíveis (não-atingíveis a partir do estado inicial).

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

- A função programa g deve ser total (a partir de qualquer estado são previstas transições para todos os símbolos do alfabeto).

- O autômato não pode apresentar transições em vazio.

Resposta: C:

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.

- Considere as seguintes afirmações:

I – Dados dois geradores de liguagens (gramáticas) e dois reconhecedores de linguagens, pode-se verificar se os dois geradores de Linguagens são equivalentes se os autômatos mínimos dos correspondentes reconhecedores são iguais.

II – Existe um algoritmo polinomial, para o qual, dada uma expressão regular, pode-se construir um autômato finito não-determinístico equivalente.

III – Existe um algoritmo polinomial , tal que para um determinado autômato finito determinístico é possível construir um autômato finito determinístico com o menor número de estados, possível.

Estão corretas as afirmações:

- Apenas I;

- Apenas I e II;

- I, II e III;

- Apenas II e III;

- Apenas III;

Resposta: C: I, II e III;

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.

- Em uma Gramática Livre de Contexto as produções podem se apresentar no lado esquerdo com:

- Quaisquer número de terminais e não-terminais;

- Apenas um terminal;

- Apenas um não-terminal;

- Um terminal desde que seja independente dos não-terminais da mesma produção;

- Um terminal desde que seja independente dos não-terminais da gramática;

Resposta: C: apenas um não-terminal;

V → w

onde V é um símbolo não terminal e w é uma cadeia composta de terminais e/ou de não terminais. O termo "livre de contexto" vem da ideia de que um não terminal V sempre pode ser trocado por w, sem tomar conta de seu contexto. Definimos uma linguagem formal como livre de contexto se existe uma gramática livre de contexto que a produz.