Linguagens Formais e automatos sumare

Prévia do material em texto

1- A descrição informal de um autômato pode ser dada da seguinte forma: Um autômato é suposto para rodar sobre uma dada sequência de entradas em passos de tempo discretos. Para cada passo, um autômato recebe uma entrada que é obtida a partir de um conjunto de símbolos ou letras, que é chamado de alfabeto. Em qualquer momento, os símbolos que servem de entrada para o autômato formam uma sequência finita de símbolos, que é chamada de palavra. Um autômato contém um conjunto finito de estados. Para cada instante de tempo durante a execução, o autômato está em um de seus estados. Para cada medida de tempo em que o autômato lê um símbolo, ele pula ou faz a transição para um próximo estado que é decidido por uma função que tem o estado atual e o símbolo mais recentemente lido como parâmetros. Esta função é chamada de função de transição. O autômato lê os símbolos da palavra de entrada, um símbolo por vez, e faz a transição de estado para estado, de acordo com a função de transição, até a palavra ser totalmente lida. Uma vez que a palavra de entrada tiver sido lida, o autômato deve parar e o estado no qual o autômato parou é chamado de estado final.
Dependendo do estado final, o autômato pode aceitar ou rejeitar uma palavra de entrada. Formalmente falando, defina que tipo de autômato está sendo descrito pela quíntupla (Q, Σ, δ, q0, F) onde Σ = Σ ∪ {ε}.
a. Um Autômato de pilha
b. Esta quíntupla não é capaz de representar um autômato.
c. Um autômato finito não determinístico
d. Um Autômato finito determinístico ok
e. Um autômato de Turing.
2- Em Ciência da Computação, mais especificamente no ramo da teoria dos autômatos, a Minimização de AFD é o processo de transformação de um dado autômato finito determinístico (AFD) em outro equivalente que tenha um número mínimo de estados. Dois AFDs são ditos equivalentes se eles descrevem a mesma linguagem regular. Vários algoritmos diferentes que realizam essa tarefa estão descritos em livros-texto padrões que abordam a teoria dos autômatos. Dado o automato a seguir, quais estados serão sempre unificados quando ocorrer uma redução deste autômato.
a)q0 e q3
b)q3 e q4
c)q2 e q3
d)q1 e q3
e)q0 e q1
3-Um Autômato finito determinístico é normalmente definido como um conceito matemático abstrato, mas devido a seu fator determinístico, ele pode ser implementado através de Hardware e Software para resolver diversos problemas específicos. Por instância, AFDs são utilizados para modelar softwares que validam entradas de usuário tal como o seu e-mail em um servidor de correio eletrônico. Analisando a sequência a seguir relativa ao algoritmo de minimização de AFD, indique qual passo não faz parte deste algoritmo.
a)Descartar todos os estados que não podem ser atingidos
b) Marcação dos estados não-equivalentes
c) Marcar os estados trivialmente não-equivalentes {estado final, estado não-final}
d) Unificação dos estados equivalentes
e) Construir a tabela com cada par de estados ocorrendo 1 vez
4) Formalmente, um autômato é definido como sendo um modelo matemático de uma máquina de estados finitos. Um autômato funciona como um reconhecedor de uma determinada linguagem e serve para modelar uma máquina simples. É usado, por exemplo, em editores de texto para reconhecer padrões. Um conceito fundamental nos autômatos é o conceito de estado. As noções de estado e sistema são tão onipresentes que foi desenvolvido um campo de conhecimento chamado Teoria dos sistemas. Dentre os autômatos existentes, os autômatos determinísticos são de grande simplicidade e possuem um poder de reconhecimento muito grande de linguagens regulares. Sendo assim, analise as assertivas a seguir e diga qual delas é uma propriedade que define um Autômato finito determinístico.
a) Em cada estado um símbolo do alfabeto permite uma única transição
b) Não existe transição direta do estado inicial para o final
c) Num estado, cada símbolo do alfabeto pode permitir mais de uma transição
d)  Somente existe um estado final
e) Nenhum estado tem transição para o estado inicial
5-Na teoria da computação, uma máquina de estados finita não-determinística ou um autômato finito não-determinístico (AFND) é uma máquina de estados finita onde para cada par de estado e símbolo de entrada pode haver vários próximos estados possíveis. Isso o distingue do autômato finito determinístico (AFD), onde o próximo estado possível é univocamente determinado. Embora AFD e AFND possuam definições distintas, pode ser mostrado na teoria formal que eles são equivalentes e, deste modo, para qualquer AFND dado, pode-se construir um AFD equivalente e vice-versa: essa é a construção do conjunto das partes. Máquinas de estados finitas não-determinísticas são generalizadas pelo autômato probabilístico, o qual atribui uma probabilidade para cada transição de estado. Tendo em vista o texto anterior, analise as afirmações a seguir e indique qual delas é falsa em relação a um AFND.
a) Pode haver uma mudança de estado sem o consumo de um símbolo da cadeia de entrada
b) Pode haver estados com mais de uma transição para um dado símbolo do alfabeto de entrada
c) Pode haver estados sem transição para algum símbolo do alfabeto de entrada
d) A transição irá depender do símbolo da cadeia de entrada e também de sua memória de estado anterior
e) Podem existir transições em vazio ε.
DEAAB
Respostas que não são:
1) Um Autômato de pilha
2) q0 e q1
3) Construir a tabela com cada par de estados ocorrendo 1 vez
4) Nenhum estado tem transição para o estado inicial
5) Pode haver estados sem transição para algum símbolo do alfabeto de entrada