home *** CD-ROM | disk | FTP | other *** search
/ CD Actual Thematic 7: Programming / CDAT7.iso / Share / Editores / Perl5 / perl / lib / site / DFA / Kleene.pm
Encoding:
Perl POD Document  |  1997-08-10  |  8.1 KB  |  329 lines
  1.  
  2. #  Copyright (c) 1996, 1997 by Steffen Beyer. All rights reserved.
  3. #  This package is free software; you can redistribute it and/or
  4. #  modify it under the same terms as Perl itself.
  5.  
  6. package DFA::Kleene;  #  DFA = Deterministic Finite Automaton
  7.  
  8. # Other modules in this series (variants of Kleene's algorithm):
  9. #
  10. # Math::MatrixBool (see "Kleene()")
  11. # Math::MatrixReal (see "kleene()")
  12.  
  13. use strict;
  14. use vars qw(@ISA @EXPORT @EXPORT_OK %EXPORT_TAGS $VERSION
  15.             $number_of_states %alphabet
  16.             %accepting_states @delta
  17.             @words %language);
  18.  
  19. require Exporter;
  20.  
  21. @ISA = qw(Exporter);
  22.  
  23. @EXPORT = qw();
  24.  
  25. @EXPORT_OK = qw(initialize define_accepting_states define_delta kleene example);
  26.  
  27. %EXPORT_TAGS = (all => [@EXPORT_OK]);
  28.  
  29. $VERSION = '1.0';
  30.  
  31. use Carp;
  32.  
  33. sub initialize
  34. {
  35.     croak "Usage: DFA::Kleene::initialize(\$number_of_states,\$alphabet)"
  36.       if (@_ != 2);
  37.  
  38.     my($number,$alpha) = @_;
  39.     my($i,$j,$k);
  40.  
  41.     croak "DFA::Kleene::initialize(): number of states must be > 0"
  42.       if ($number <= 0);
  43.     croak "DFA::Kleene::initialize(): alphabet must comprise at least one character"
  44.       if (length($alpha) == 0);
  45.  
  46.     $number_of_states = $number;
  47.  
  48.     undef %alphabet;
  49.     undef %accepting_states;
  50.     undef @delta;
  51.     undef @words;
  52.     undef %language;
  53.  
  54.     for ( $i = 0; $i < length($alpha); $i++ )
  55.     {
  56.         $alphabet{substr($alpha,$i,1)} = 1;
  57.     }
  58.  
  59.     for ( $i = 1; $i <= $number_of_states; $i++ )
  60.     {
  61.         $delta[$i] = { };
  62.         $words[$i] = [ ];
  63.         for ( $j = 1; $j <= $number_of_states; $j++ )
  64.         {
  65.             $words[$i][$j] = [ ];
  66.             for ( $k = 0; $k <= $number_of_states; $k++ )
  67.             {
  68.                 $words[$i][$j][$k] = { };
  69.             }
  70.         }
  71.     }
  72. }
  73.  
  74. sub define_accepting_states
  75. {
  76.     croak "Usage: DFA::Kleene::define_accepting_states(\@accepting_states)"
  77.       if (@_ < 1);
  78.  
  79.     my(@final) = @_;
  80.     my($state);
  81.  
  82.     undef %accepting_states;
  83.     foreach $state (@final)
  84.     {
  85.         croak "DFA::Kleene::define_accepting_states(): state $state not in [1..$number_of_states]"
  86.           if (($state < 1) || ($state > $number_of_states));
  87.         $accepting_states{$state} = 1;
  88.     }
  89. }
  90.  
  91. sub define_delta
  92. {
  93.     croak "Usage: DFA::Kleene::define_delta(\$state1,\$character,\$state2)"
  94.       if (@_ != 3);
  95.  
  96.     my($state1,$character,$state2) = @_;
  97.  
  98.     croak "DFA::Kleene::define_delta(): state $state1 not in [1..$number_of_states]"
  99.       if (($state1 < 1) || ($state1 > $number_of_states));
  100.     croak "DFA::Kleene::define_delta(): state $state2 not in [1..$number_of_states]"
  101.       if (($state2 < 1) || ($state2 > $number_of_states));
  102.     croak "DFA::Kleene::define_delta(): only single character or empty string permitted"
  103.       if (length($character) > 1);
  104.     croak "DFA::Kleene::define_delta(): character is not contained in alphabet"
  105.       if ($character && !($alphabet{$character}));
  106.     croak "DFA::Kleene::define_delta(): \$delta[$state1]{'$character'} already defined"
  107.       if (defined $delta[$state1]{$character});
  108.  
  109.     $delta[$state1]{$character} = $state2;
  110. }
  111.  
  112. sub kleene
  113. {
  114.     croak "Usage: DFA::Kleene::kleene()"
  115.       if (@_ != 0);
  116.  
  117.     my($i,$j,$k);
  118.     my($state,$word,$word1,$word2,$word3);
  119.  
  120.     for ( $i = 1; $i <= $number_of_states; $i++ )
  121.     {
  122.         for ( $j = 1; $j <= $number_of_states; $j++ )
  123.         {
  124.             foreach $_ (keys %{$delta[$i]})
  125.             {
  126.                 if ($delta[$i]{$_} == $j)
  127.                 {
  128.                     $words[$i][$j][0]{$_} = 1;
  129.                 }
  130.             }
  131.             if ($i == $j) { $words[$i][$j][0]{''} = 1; }
  132.         }
  133.     }
  134.  
  135.     for ( $k = 1; $k <= $number_of_states; $k++ )
  136.     {
  137.         for ( $i = 1; $i <= $number_of_states; $i++ )
  138.         {
  139.             for ( $j = 1; $j <= $number_of_states; $j++ )
  140.             {
  141.                 foreach $word (keys %{$words[$i][$j][$k-1]})
  142.                 {
  143.                     $words[$i][$j][$k]{$word} = 1;
  144.                 }
  145.                 foreach $word1 (keys %{$words[$i][$k][$k-1]})
  146.                 {
  147.                     foreach $word2 (keys %{$words[$k][$k][$k-1]})
  148.                     {
  149.                         foreach $word3 (keys %{$words[$k][$j][$k-1]})
  150.                         {
  151.                             if ($word2)
  152.                                 { $word = "${word1}(${word2})*${word3}"; }
  153.                             else
  154.                                 { $word = "${word1}${word3}"; }
  155.                             $words[$i][$j][$k]{$word} = 1;
  156.                         }
  157.                     }
  158.                 }
  159.             }
  160.         }
  161.     }
  162.     undef %language;
  163.     foreach $state (keys %accepting_states)
  164.     {
  165.         # Note that the following assumes state #1 to be the "start" state:
  166.  
  167.         foreach $word (keys %{$words[1][$state][$number_of_states]})
  168.         {
  169.             $language{$word} = 1;
  170.         }
  171.     }
  172.     return( sort(keys %language) );
  173. }
  174.  
  175. sub example
  176. {
  177.     &initialize(6,"ab");
  178.     &define_accepting_states(2,3,4,5);
  179.     &define_delta(1,'a',4);
  180.     &define_delta(1,'b',6);
  181.     &define_delta(2,'a',2);
  182.     &define_delta(2,'b',5);
  183.     &define_delta(3,'a',6);
  184.     &define_delta(3,'b',3);
  185.     &define_delta(4,'a',2);
  186.     &define_delta(4,'b',5);
  187.     &define_delta(5,'a',4);
  188.     &define_delta(5,'b',3);
  189.     &define_delta(6,'a',6);
  190.     &define_delta(6,'b',6);
  191.  
  192.     # should return something equivalent to:
  193.     #         (a(a)*b)*a(a)*(b)*
  194.     # which is the same as ((a+)b)*(a+)b*
  195.  
  196.     foreach $_ ( &kleene() )
  197.     {
  198.         print "'$_'\n";
  199.     }
  200. }
  201.  
  202. 1;
  203.  
  204. __END__
  205.  
  206. =head1 NAME
  207.  
  208. DFA::Kleene - Kleene's Algorithm for Deterministic Finite Automata
  209.  
  210. Calculates the "language" (set of words) accepted
  211. (= recognized) by a Deterministic Finite Automaton
  212.  
  213. See L<Math::Kleene(3)> for the theory behind this algorithm!
  214.  
  215. =head1 SYNOPSIS
  216.  
  217. =over 4
  218.  
  219. =item *
  220.  
  221. C<use DFA::Kleene qw(initialize define_accepting_states>
  222. C<define_delta kleene example);>
  223.  
  224. =item *
  225.  
  226. C<use DFA::Kleene qw(:all);>
  227.  
  228. =item *
  229.  
  230. C<&initialize(6,"ab");>
  231.  
  232. Define the number of states (state #1 is the "start" state!) of your
  233. Deterministic Finite Automaton and the alphabet used (as a string
  234. containing all characters which are part of the alphabet).
  235.  
  236. =item *
  237.  
  238. C<&define_accepting_states(2,3,4,5);>
  239.  
  240. Define which states are "accepting states" in your Deterministic Finite
  241. Automaton (list of state numbers).
  242.  
  243. =item *
  244.  
  245. C<&define_delta(1,'a',4);>
  246.  
  247. Define the state transition function "delta" (arguments are: "from" state,
  248. character (or empty string!) read during the transition, "to" state).
  249.  
  250. You need several calls to this function in order to build a complete
  251. transition table describing your Deterministic Finite Automaton.
  252.  
  253. =item *
  254.  
  255. C<@language = &kleene();>
  256.  
  257. Returns a (sorted) list of regular expressions describing the language
  258. (= set of patterns) recognized ("accepted") by your Deterministic Finite
  259. Automaton.
  260.  
  261. =item *
  262.  
  263. C<&example();>
  264.  
  265. Calculates the language of a sample Deterministic Finite Automaton.
  266.  
  267. Prints a (sorted) list of regular expressions which should be equivalent
  268. to the following regular expression:
  269.  
  270.             (a(a)*b)*a(a)*(b)*
  271.  
  272. This is the same as
  273.  
  274.             ((a+)b)*(a+)b*
  275.  
  276. =back
  277.  
  278. =head1 DESCRIPTION
  279.  
  280. The routines in this module allow you to define a Deterministic Finite
  281. Automaton and to compute the "language" (set of "words" or "patterns")
  282. accepted (= recognized) by it.
  283.  
  284. Actually, a list of regular expressions is generated which describe the
  285. same language (set of patterns) as the one accepted by your Deterministic
  286. Finite Automaton.
  287.  
  288. The output generated by this module can easily be modified to produce
  289. Perl-style regular expressions which can actually be used to recognize
  290. words (= patterns) contained in the language defined by your Deterministic
  291. Finite Automaton.
  292.  
  293. Other modules in this series (variants of Kleene's algorithm):
  294.  
  295. =over 4
  296.  
  297. =item *
  298.  
  299. Math::MatrixBool (see "Kleene()")
  300.  
  301. =item *
  302.  
  303. Math::MatrixReal (see "kleene()")
  304.  
  305. =back
  306.  
  307. =head1 SEE ALSO
  308.  
  309. Math::MatrixBool(3), Math::MatrixReal(3), Math::Kleene(3),
  310. Set::IntegerRange(3), Set::IntegerFast(3), Bit::Vector(3).
  311.  
  312. =head1 VERSION
  313.  
  314. This man page documents "DFA::Kleene" version 1.0.
  315.  
  316. =head1 AUTHOR
  317.  
  318. Steffen Beyer <sb@sdm.de>.
  319.  
  320. =head1 COPYRIGHT
  321.  
  322. Copyright (c) 1996, 1997 by Steffen Beyer. All rights reserved.
  323.  
  324. =head1 LICENSE
  325.  
  326. This package is free software; you can redistribute it and/or
  327. modify it under the same terms as Perl itself.
  328.  
  329.