NAME

Computer::Theory::FSA - Computer theory of Finite State Automanton.

SYNOPSIS

 #!/usr/bin/perl
 
 use Computer::Theory::FSA;
 
 my $FA = new Computer::Theory::FSA();
 
 $FA->addState("q0");
 $FA->addState("q1");
 $FA->addState("q2");
 $FA->addState("q3");
 $FA->addAlphabet("a");
 $FA->addAlphabet("b");
 $FA->setStarting("q0");
 $FA->addFinal("q3");
 $FA->addTransition("a","q0","q1");
 $FA->addTransition("a","q1","q2");
 $FA->addTransition("a","q2","q3");
 $FA->addTransition("b","q0","q0");
 
 my $valide = $FA->DFA($word);

DESCRIPTION

"A Finite State Automaton is an abstract machine used in the study of computation and languages that has only a finite, constant amount of memory (the state). It can be conceptualised as a directed graph. There are a finite number of states, and each state has transitions to zero or more states. There is an input string that determines which transition is followed. Finite state machines are studied in automata theory, a subfield of theoretical computer science". [Wikipedia - Mon Jun 23 2003]

METHODS

new

The constructor method.

 my $FA = new Computer::Theory::FSA();

addState

Set new state in the list of states.

 $FA->addState("qX");

delState

Remove state in the list of states.

 $FA->delState("qX");

getState

Get the list of states.

 foreach my $state ($FA->getState()) {
    print $state." ";
 }

addAlphabet

Set new caracter in the list of alphabet.

 $FA->addAlphabet("x");

delAphabet

Remove caracter in the list of alphebet.

 $FA->delAlphabet("x");

getAlphabet

Get the list of alphabet.

 foreach my $caracter ($FA->getAlphabet()) {
    print $i." ";
 }

setStarting

Attribute starting state.

 $FA->setStarting("qX");

getStarting

Get starting state.

 my $starting = $FA->getStarting();

addFinal

Set new state in the list of final states.

 $FA->addFinal("qX");

delFinal

Remove state in the list of final states.

 $FA->delFinal("qX");

getFinal

Get the list of final states.

 foreach my $fstate ($FA->getFinal()) {
    print $fstate." ";
 }

addTransition

Set new transition in the list of transitions.

 $FA->addTransition("x","qX","qY");

delTransition

Remove transition in the list of transitions.

 $FA->delTransition("x","qX","qY");
 $FA->delTransition("x","qX");

getTransition

Get the list of transitions.

 foreach my $caracter (sort keys %tt) {
    foreach my $from (sort keys %{$tt{$caracter}}) {
       print "             $caracter - $from => ";
       foreach my $destine (@{$tt{$caracter}{$from}}) {
          print "$destine ";
       }
       print "\n";
    }
 }

DFA

Algorithm of valide the Deterministic Finite Automaton. "The machine starts in the start state and reads in a string of symbols from its alphabet. It uses the transition function T to determine the next state using the current state and the symbol just read. If, when it has finished reading, it is in an accepting state, it is said to accept the string, otherwise it is said to reject the string. The set of strings it accepts form a language, which is the language the DFA recognises". [Wikipedia - Mon Jun 23 2003]

 my $valide = $FA->DFA('xxx');

SEE ALSO

Wikipedia documentation.

AUTHOR

Fabiano Reese Righetti <frighetti@cpan.org>

COPYRIGHT

Copyright 2003 Fabiano Reese Righetti <frighetti@cpan.org> All rights reserved.

This code is free software released under the GNU General Public License, the full terms of which can be found in the "COPYING" file in this directory.