Aula 4 - Automatos e Linguagens Formais

Prévia do material em texto

�PAGE �
�PAGE �7�
Autômatos e Linguagens Formais - Aula 4
Autômatos
Considerar o problema de se elaborar um modelo computacional para representar uma máquina de bebidas.
1º passo: identificar os elementos básicos da máquina de bebidas.
2º passo: estabelecer as relações (ações) entre os elementos básicos da máquina.
3º passo: escolher um modelo computacional para definir a máquina de bebidas.
4º passo: modelo escolhido ( máquina de estados finitos (autômatos)
5º passo: elaborar um rascunho do modelo utilizando uma representação similar à grafos.
Modelagem: dado um determinado problema, identificar o problema suas características e elementos buscando um modelo que retrate fielmente os aspectos desejados.
Ao final deve-se ter uma representação da solução computacional para o problema.
Teoria de Autômatos
Autômatos lidam com definições e propriedades de modelos matemáticos (formais) de computação.
Modelos aplicados em diversas áreas da ciência da computação. Dentre elas, cita:
Processamento de texto, compiladores, desenvolvimento de hardware;
Linguagem de programação, inteligência artificial;
Primeiro uso: modelagem de redes neurais.
Desenvolvimento do aprendizado algorítmico;
Estudo dos fundamentos da computação.
Autômatos
São sistemas de estados finitos utilizados para o reconhecimento de palavras. Como entrada, recebem a palavra a ser analisada, e, como saída, informam se a palavra é aceita ou rejeitada.
 
Um Autômato Finito (AF) é composto dos seguintes elementos:
Fita
Unidade de Controle (Cabeça de leitura e Conjunto de estados)
Programa
Fita:
Inicialmente é ocupada por toda a palavra. Cada símbolo da palavra fica gravado em uma célula (posição) da fita. Não é possível gravar caracteres adicionais.
Unidade de Controle:
Inicialmente a cabeça de leitura fica posicionada na primeira célula da fita. A cabeça de leitura se move exclusivamente para a direita.
Os estados de um autômato podem ser representados da seguinte forma:
Função de Transição ou programa:
Determina a mudança de estado do autômato M, dependendo do estado atual e do símbolo lido na fita.
Fita
	a
	a
	b
	a
	b
Aceitação de palavras:
Uma palavra é aceita por um AF se, após ser processada, o estado atual for final. Caso contrário, a palavra será rejeitada.
Linguagem aceita:
A linguagem aceita por um M ( L(M) ou Aceita(M) ), é o conjunto de palavras que são aceitas por este AF.
Ex.: Dado o AF M1 a seguir
�
L(M1) = { w ( {0, 1}* | 0 é prefixo de w }. Ou seja, A linguagem aceita pelo AF M1 é composta do conjunto de palavras que podem ser formadas com 0 ou mais símbolos do alfabeto {0, 1}, que têm o 0 como prefixo.
Autômatos Equivalentes:
Dois autômatos M1 e M2 distintos são equivalentes, se as linguagens aceitas por eles forem iguais.
Ex.: O AF M2 abaixo é equivalente ao AF M1 do exemplo anterior.
�
Autômatos Finitos Determinísticos (AFD):
Um AFD pode ser representado esquematicamente conforme a Figura acima: os símbolos que compõem a palavra a ser testada encontram-se escritos numa fita de entrada, dividida em células, onde cada símbolo ocupa exatamente uma célula. Há um controle finito composto pelos estados possíveis para o autômato, sendo que existe um marcador que indica o estado atual. Além disso, há uma cabeça de leitura que lê um símbolo por vez da fita.
Finito. O autômato é dito finito porque o conjunto de estados possíveis (Q) é finito.
Determinístico. O autômato é determinístico quando dado o estado atual de M, ao ler um determinado símbolo na finita de entrada existe apenas um próximo estado possível.
Estado Inicial. O estado inicial q0 indica que ao “ligarmos” o AFD, o marcador automaticamente se posiciona no estado q0, antes de ler qualquer símbolo da fita de entrada. Só pode existir um único estado inicial.
Aceitação. Uma palavra é reconhecida (ou aceita) quando o AFD após ler todos os símbolos contidos na fita de entrada, o marcador se encontrar em um estado final. Ao contrário do estado inicial, podem existir vários estados finais.
Rejeição. Uma palavra é rejeitada quando após ler todos os símbolos da fita de entrada, o marcador não se encontrar em um estado final ou quando não existe uma transição definida para um símbolo a ser lido, estando o autômato num determinado estado.
Máquina de Estados Finitos. Alguns autores denominam os AFDs de máquinas de estados finitos.
Grafo Orientado. Comumente representa-se a função programa (() utilizando-se um grafo orientado. A Figura abaixo apresenta o grafo correspondente à função programa do AFD do exemplo anterior.
Os nós do grafo representam os estados possíveis do AFD enquanto as arestas orientadas representam as transições. A origem de uma seta indica o estado atual. O símbolo a ser lido é colocado sobre a seta.
Este AFD reconhece a linguagem L = { w | w é formada por uma seqüência de um ou
mais a’s seguido de exatamente um b sobre (*}, onde ( = {a,b}. 
Autômatos Finitos Não Determinísticos (AFND):
Definição. Um autômato finito não-determinístico (AFND) é similar a um AFD, porém existe pelo menos um estado tal que ao ler um mesmo símbolo há mais de uma possibilidade de estado destino. Considere o autômato abaixo:
No autômato da Figura anterior, existem duas transições de estado possíveis ao ler o símbolo a estando o autômato no estado q0.
Aceitação. Uma cadeia é aceita por um AFND se testando-se todas as transições possíveis à medida que se lê a cadeia, o AFND pára em um estado final após ler toda a cadeia para algum caminho das transições. Assim, o não-determinismo do próximo estado pode ser interpretado como um teste de todas as possibilidades.
Exemplos de cadeias aceitas pelo AFND dado anteriormente: a, ac, ab, abcc, ...
Rejeição. Uma cadeia é rejeita por um AFND se nenhum caminho de transições leva o autômato a um estado final após ler toda a cadeia.
Exemplos de cadeias rejeitadas pelo AFND dado anteriormente: b, bc, abb, aca, ...
Exercício 
	Leia a Bibliografia dada a seguir e procure por:
Definição de Autômatos 
Aplicações de Autômatos 
Exemplos e Exercícios com Autômatos
Bibliografia:
BLAUTH Paulo. Linguagens Formais e Autômatos. Série Livros Didáticos, Sagra Luzzato Editores, Porto Alegre, 2002.
HOPCROFT, J.E., Ullman, J.D., Motwani, R., Introdução a Teoria dos Autômatos, Linguatens e Computação, Rio de Janeiro, Editora Campus, 2002.
HOPCROFT, J.E., Ullman, J.D., Motwani, R., Introduction to Automata Theory, Languagens, and Computation, New York, Addison Wesley, 2001 
GALLI, HAREL, DAVID. Algoritmics, the spirit of computing, Addison Wesley, Worringhan, 1987. 
LEWIS/PAPADIMITRIOU. Elements of the theory of computation. Prentice-Hall, 1981.
0, 1
0, 1
q2
0
q1
q0
0, 1
0
q1
q0
Unidade de Controle
Estado atual
q
Inicial
q
Final
q
Inicial e Final
q
Comum
q
 Rejeita
 Aceita
Palavra
�M