DFA::Kleene - Kleene's Algorithm for Deterministic Finite Automata

Calculates the "language" (set of words) accepted (= recognized) by a Deterministic Finite Automaton

See Math::Kleene(3) for the theory behind this algorithm!

• use DFA::Kleene qw(initialize define_accepting_states define_delta kleene example);
• use DFA::Kleene qw(:all);
• &initialize(6,"ab");
  
  Define the number of states (state #1 is the "start" state!) of your Deterministic Finite Automaton and the alphabet used (as a string containing all characters which are part of the alphabet).
• &define_accepting_states(2,3,4,5);
  
  Define which states are "accepting states" in your Deterministic Finite Automaton (list of state numbers).
• &define_delta(1,'a',4);
  
  Define the state transition function "delta" (arguments are: "from" state, character (or empty string!) read during the transition, "to" state).
  
  You need several calls to this function in order to build a complete transition table describing your Deterministic Finite Automaton.
• @language = &kleene();
  
  Returns a (sorted) list of regular expressions describing the language (= set of patterns) recognized ("accepted") by your Deterministic Finite Automaton.
• &example();
  
  Calculates the language of a sample Deterministic Finite Automaton.
  
  Prints a (sorted) list of regular expressions which should be equivalent to the following regular expression:
  
  

              (a(a)*b)*a(a)*(b)*
  
  

  
  
  This is the same as
  
  

              ((a+)b)*(a+)b*
  
  

The routines in this module allow you to define a Deterministic Finite Automaton and to compute the "language" (set of "words" or "patterns") accepted (= recognized) by it.

Actually, a list of regular expressions is generated which describe the same language (set of patterns) as the one accepted by your Deterministic Finite Automaton.

The output generated by this module can easily be modified to produce Perl-style regular expressions which can actually be used to recognize words (= patterns) contained in the language defined by your Deterministic Finite Automaton.

Other modules in this series (variants of Kleene's algorithm):

• Math::MatrixBool (see "Kleene()")
• Math::MatrixReal (see "kleene()")

Math::MatrixBool(3), Math::MatrixReal(3), Math::Kleene(3), Set::IntegerRange(3), Set::IntegerFast(3), Bit::Vector(3).

This man page documents "DFA::Kleene" version 1.0.

Steffen Beyer <sb@sdm.de>.

Copyright (c) 1996, 1997 by Steffen Beyer. All rights reserved.

This package is free software; you can redistribute it and/or modify it under the same terms as Perl itself.