Automatos Finitos

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

16/04/2012 
1 
 
 
 
 Linguagens Formais e Autômatos 
Autômatos Finitos com 
Movimentos Vazios 
 
Profa. Lúcia Helena de Magalhães 
lucia.magalhaes@ifsudestemg.edu.br 
 
 
Autômatos Finitos com Movimentos 
Vazios 
  Autômatos Finitos com Movimentos Vazios ou 
Autômatos Finitos com Arcos- são arcos de 
transição em autômatos finitos não 
determinístico (AFN) que permitem a mudança 
de estado sem consumir símbolo da cadeia. 
 Assim como os autômatos não determinístico, a 
existência de arcos- não aumenta o poder 
computacional no reconhecimento de 
linguagens. 
 
Autômatos Finitos com Movimentos 
Vazios 
 
 Movimentos vazios constituem uma 
generalização dos modelos de máquinas 
não determinísticas. 
 Um movimento vazio é uma transição 
sem leitura de símbolo algum da fita. 
 Uma das vantagens e o fato de facilitar 
algumas construções e demonstrações 
relacionadas com os autômatos (Menezes, 
1997). 
Autômatos Finitos com Movimentos 
Vazios 
 Exemplo: 
 
 
 
 O autômato vai do estado p para o estado 
q sem ler um símbolo de entrada. 
 
Pode ser 
 
Autômatos Finitos com Movimentos 
Vazios 
 A diferença para os AFNDs é a função de 
transição. 
 Além dos símbolos, agora também está 
definida para ε (ausência de símbolo). 
Nenhum 
símbolo lido! 
 Quando um autômato transita em vazio, 
isso significa que ele muda de estado sem 
consultar a cadeia de entrada. 
 A diferença para os AFNDs é a função de 
transição. 
 Além dos símbolos, agora também está 
definida para ε (ausência de símbolo). 
 
Autômatos Finitos com Movimentos 
Vazios 
 
16/04/2012 
2 
Autômatos Finitos com Movimentos 
Vazios 
 Definição Formal 
 Um autômato finito com movimentos vazios 
(AF) e uma 5-upla (S, Q, , q0, F), onde: 
 S e um alfabeto finito. 
 Q e um conjunto finito de estados. 
  : É a função de transição. 
 Q0 Q e o estado inicial. 
 F  Q e o conjunto de estados de aceitação. 
Autômatos Finitos com Movimentos 
Vazios 
 Desenvolver um AF que aceite palavras 
na forma a*b*: 
 M = ({1, 2}, {a, b}, , 1, {2}) 
A função de transição 
pode ser representada 
através de um grafo 
ou de tabela. 
Autômatos Finitos com Movimentos 
Vazios 
 Funcionamento 
 O processamento de um AF e análogo ao 
de um AFN: 
◦ Adicionalmente, o processamento de uma 
transição para uma entrada vazia também é não 
determinística; 
◦ Assim, um AF ao processar uma entrada vazia 
assume simultaneamente os estados destino e 
origem; 
◦ Ou seja, a origem de um movimento vazio 
sempre é um caminho alternativo. 
Autômatos Finitos com Movimentos 
Vazios 
 Exemplo: 
◦ Suponha um autômato que reconhece a 
expressão que é a soma de um inteiro positivo 
ou negativo com um decimal positivo. 
. 
Autômatos Finitos com Movimentos 
Vazios 
 Testar o autômato com a expressão: -12+2.6 
. 
Autômatos Finitos com Movimentos 
Vazios 
 Pratique! 
◦ Mostre como o autômato finito não-
determinístico com transições vazias (AFND) 
D se comporta ao receber a palavra abc. 
◦ Para isso, mostre os conjuntos de estados 
atingidos após a leitura de cada símbolo da 
palavra. 
◦ Lembre-se de considerar as transições  antes 
e depois de fazer a transição para os símbolos 
da palavra. 
16/04/2012 
3 
Autômatos Finitos com Movimentos 
Vazios 
Exercício 
 Quais palavras são aceitas pelo autômato? 
 
Equivalência AFε / AFN 
 Exemplo 1: 
 Seja o seguinte autômato com arcos-: 
 
 
 
 O  é especificado pela tabela: 
  a b  
q0 {q0}  {q1} 
q1  {q1}  
Equivalência AFε / AFN 
 O AFN equivalente a este AF é obtido num 
processo análogo à obtenção do autômato 
determinístico, reescrevendo a tabela do  da 
seguinte forma: 
1. Elimine-se a coluna do , incluindo em cada 
estado que possui arco-  o destino do mesmo. 
2. Incluem-se os demais estados, seguindo o mesmo 
procedimento: 
 a b 
q0 {q0, q1}  
q1  {q1} 
Equivalência AFε / AFN 
 Seja o seguinte autômato com arcos-. 
 
 
 
 
 
 Este AFε M = {q0, q1, q2,q3,q4,q5,q6,q7}, {a, b, c}, , 
{q0}, {q4}) processa a linguagem L={w  {a, b, c)* e 
w termina com a, bb ou ccc}. O  é especificado pela 
tabela a seguir: 
 
Equivalência AFε / AFN 
 a b c  
q0 
{q0} {q0} 
 
{q0} 
 
{q0, q2, q5} 
 
q1 
{q4}    
q2 
 {q3}   
q3 
 {q4}   
q4 
    
q5 
  {q6}  
q6 
  {q7}  
q7 
  {q4}  
16/04/2012 
4 
Equivalência AFε / AFN 
 a b c 
q0 
{q0, q1, q2, q5, q4} {q0, q1, q2, q3, q5} {q0, q1, q2, q5, q6} 
 
q1 
{q4}   
q2 
 {q3}  
q3 
 {q4}  
q4 
   
q5 
  {q6} 
q6 
  {q7} 
q7 
  {q4} 
O AFN equivalente a este AF é obtido: 
 
Todo AFε pode ser 
simulado por um 
AFN 
Equivalência AFε / AFN 
Exercício 
◦ Criar AFN equivalente ao afε.