#!/usr/bin/perl -w
#
# Autômato Finito
#
#    Trabalho   acadêmico  para  a  disciplina  de  Linguagens Formais,
# Autômatos e Computabilidade, ministrada pelo professor Norldir Kunkel
# na  União  Pan-Americana  de  Ensino,  no  qual propõe-se elaborar um
# algoritmo  para  AFN (Autômato Finito Determinístico) e AFN (Autômato
# Finito Não determinístico).
#
# Dados necessários:
#    { Z, Q, I, F, K }
#      |  |  |  |  `---> Tabela de funções de transição de estados.
#      |  |  |  `------> Conjunto de estados finais/terminais.
#      |  |  `---------> Estado inicial.
#      |  `------------> Conjunto finito de estados.
#      `---------------> Alfabeto.
#
# Versões (http://cascavel.pm.org/~fabiano/):
#  0.1a - 29/03/2003 - AFD funcional.
#  0.1b - 30/03/2003 - Algoritmo genérico e funcional para AFD/AFN.
#  0.1c - 31/03/2003 - Desenvolvido interatividade com o usuário.
#                      Corrigido  bug  no  loop  de  transições no qual
#                      definia  a  palavra  como  válida mesmo quando a
#                      última transição retornava inválida.
#
# Exemplo:
# $ perl af.pl
#  Autômato Finito Determinístico e Não determinístico
#  Obs.: Separe por "," (vírgula) cada item.
#
#                                   Alfabeto: a,b
#                 Conjunto finito de estados: q0,q1,q2,q3
#                             Estado inicial: q0
#       Conjunto de estados finais/terminais: q3
#  Tabela de funções de transição de estados:
#                                   a - q0 => q0,q1
#                                   a - q1 => q2
#                                   a - q2 => q3
#                                   a - q3 => 
#                                   b - q0 => q0
#                                   b - q1 => 
#                                   b - q2 => 
#                                   b - q3 => 
#                      Palavra a ser testada: aaabababaaa
#                                          -> A palavra é válida!
#                      Palavra a ser testada: 
# $
#
# Copyright 2003 Fabiano Reese Righetti <fabiano@cascavel.pm.org>
# All rights reserved.
#
# English (http://www.gnu.org/licenses/gpl.txt):
#     This  program  is  free software; you can redistribute it and/or
# modify  it  under  the  terms  of  the GNU General Public License as
# published  by  the Free Software Foundation; either version 2 of the
# License, or (at your option) any later version.
#    This  program  is distributed in the hope that it will be useful,
# but  WITHOUT  ANY  WARRANTY;  without  even  the implied warranty of
# MERCHANTABILITY  or  FITNESS  FOR A PARTICULAR PURPOSE.  See the GNU
# General Public License for more details.
#
# Português (http://www.magnux.org/doc/GPL-pt_BR.txt):
#     Este programa é um software livre; você pode redistribuí-lo e/ou 
# modificá-lo  dentro  dos  termos  da  Licença Pública Geral GNU como 
# publicada  pela  Fundação  do  Software  Livre (FSF); na versão 2 da 
# Licença, ou (na sua opinião) qualquer versão.
#    Este programa é distribuído na esperança que possa ser  útil, mas
# SEM  NENHUMA  GARANTIA;  sem  uma  garantia implícita de ADEQUAÇÂO a
# qualquer  MERCADO ou APLICAÇÃO EM PARTICULAR. Veja a Licença Pública
# Geral GNU para maiores detalhes.

use strict;

my (
    $Inicial, $Palavra,
    @Alfabeto, @Estados, @Finais, @Palavra,
    %Tabela,
   );

print " Autômato Finito Determinístico e Não determinístico\n";
print " Obs.: Separe por \",\" (vírgula) cada item.\n\n";
print "                                  Alfabeto: ";
chomp($_ = <STDIN>); @Alfabeto = split(/,/);
print "                Conjunto finito de estados: ";
chomp($_ = <STDIN>); @Estados = split(/,/);
print "                            Estado inicial: ";
chomp($Inicial = <STDIN>);
print "      Conjunto de estados finais/terminais: ";
chomp($_ = <STDIN>); @Finais = split(/,/);
print " Tabela de funções de transição de estados:\n";
for my $C (@Alfabeto) {
   for my $E (@Estados) {
      print "                                  $C - $E => ";
      chomp($Tabela{$C}{$E} = <STDIN>);
   }
}

do {
   print "                     Palavra a ser testada: ";
   chomp($Palavra = <STDIN>); @Palavra = split(//, $Palavra);

   if ($Palavra ne '') {
   print "                                         -> A palavra é ";
      print ${&AF($Inicial, 0)}[0] ? "válida!\n" : "inválida!\n";
   }
} while ($Palavra ne '');

# Autômato Finito Determinístico
#    É  um  sistema  de  estados  finitos  onde  para  cada símbolo do
# alfabeto existe somente uma saída de um estado n.
#
# Exemplo:                                      .-.
#            a             a             a      V | a
# ->( 0 )-------->( 1 )-------->( 2 )-------->((3))
#                                               ^ | b
#                                               '-'
# Autômato Finito Não determinístico
#    De um determinado estado podem sair duas ou mais transições com o
# mesmo símbolo para estados diferentes.
#
# Exemplo:          .-.
#            a      V | a  a             a
# ->( 0 )-------->( 1 )-------->( 2 )-------->((3))
#                   ^ | b
#                   '-'
sub AF {
   #    Deve  ser  passado  por  parâmetro  o estado  e  a  posição do
   # caractere atual da palavra.
   my ($Estado, $Posicao) = my ($EstadoTMP, $PosicaoTMP) = @_;

   # Indicia a situação da palavra (0 para inválida e 1 para válida).
   my $Situacao = 1;

   # Verifica se existe o estado.
   if ((defined $Tabela{$Palavra[$Posicao]}{$Estado}) and
       ($Tabela{$Palavra[$Posicao]}{$Estado} ne '')) {
      # Divide as transições possíveis.
      my @Opcoes = split(/,/, $Tabela{$Palavra[$Posicao]}{$Estado});
      
      # Percorre cada transição.
      for (my $j = 0; $j <= $#Opcoes; $j++) {
         #    Se  já foi atingido a última posição da palavra, pega-se
         # e atribui o estado atual.
         ($Situacao, $Estado) = $Posicao < $#Palavra ?
                                @{&AF( $Opcoes[$j], ++$Posicao)} :
                                ($Situacao, $Opcoes[$j]);
         #    Se  a  transição  percorrida  for  válida,  sai do loop,
         # senão, define os valores iniciais as variáveis.
           if ($Situacao) { last; }
         else { ($Situacao, $Estado, $Posicao) = (1, $j == $#Opcoes ?
                                                     '' : $EstadoTMP,
                                                     $PosicaoTMP); }
      }
   # Caso contrário, define a palavra como inválida.
   } else {
      ($Situacao, $Estado) = (0, '');
   }

   #    Se  a  palavra  ainda  é  válida,  necessita-se verificar se o
   # estado atual pertence aos estados finais/terminais.
   if ($Situacao) {
      for (my $i = 0; $i <= $#Finais; $i++) {
         if ($Estado ne $Finais[$i]) {
            $Situacao = 0;
         } else {
            $Situacao = 1;
            last;
         }
      }
   }

   return([$Situacao, $Estado]);
}