Generated: May 24, 2003, 13:23:13Copyright ©2003, Kurt NørmarkThe local LAML software home page

Reference Manual of the LAML Final State Automaton library

Kurt Nørmark ©    normark@cs.auc.dk    Department of Computer Science    Aalborg University    Denmark    

Master index
Source file: lib/final-state-automaton.scm
LAML Version 20.00 (May 24, 2003, full)

This is a Scheme library that support Final State Automatons, both non-deterministic and deterministic. The library includes a function that generates a deterministic automaton from a non-deterministic automaton. Another central function is automaton-accepts? which accepts or rejects a list of input symbols in a DFA. The generated automata are both compact and fast, because they make apply a rather efficient transition lookup in a sorted vector.

Table of Contents:
1. Automaton construction and selection.3. Transitions 5. DFA construction from NFA.
2. State and transition predicates.4. Acceptance predicate.

Alphabetic index:
automaton-accepts?(automaton-accepts? automaton symbol-list)Does automaton accepts the input symbol-list.
epsilon-symbolepsilon-symbolThe denotation for the empty symbol.
epsilon-symbol?(epsilon-symbol? s)Is the symbol s an epsilon symbol?
epsilon-transition?(epsilon-transition? trans)Is the transition trans an epsilon transition?
final-states-of-finite-state-automaton(final-states-of-finite-state-automaton aut)Return the list of final states of an automaton.
from-state-of-transition(from-state-of-transition trans)Return the from-state of the transition.
make-automaton-transition(make-automaton-transition in-state symbol out-state)Make a final state transition
make-finite-state-automaton(make-finite-state-automaton start-state accept-state-list transitions [given-symbol-map])Make a finite state automaton with a given start-state, a list of accept states, and a set of transitions - a list.
start-state-of-finite-state-automaton(start-state-of-finite-state-automaton aut)Return the start state of an automaton.
state-equal?(state-equal state1 state2).The equality used for states in a final state automaton.
state-leq?(state-leq? state1 state2)A leq? function on states.
state-lt?(state-lt state1 state2)A less than function on states.
subset-construction(subset-construction nfa [support-epsilon-moves?])Return an equivalent DFA from the non-deterministic NFA passed as first parameter.
symbol-equal?(symbol-equal? sym1 sym2).The equality used for symbols in a final state automaton.
symbol-map-of-finite-state-automaton(symbol-map-of-finite-state-automaton aut)Return the symbol map of an automaton.
symbol-of-transition(symbol-of-transition trans)Return the symbol of the transtion.
to-state-of-transition(to-state-of-transition trans)Return the to-state of the transition.
transition-leq?(transition-leq? trans1 trans2)A leq? function on transitions.
transition-list-of-finite-state-automaton(transition-list-of-finite-state-automaton aut)Return the transitions - as a list - of an automaton.
transitions-of-finite-state-automaton(transitions-of-finite-state-automaton aut)Return the transitions - a sorted vector - of an automaton.

 

1.   AUTOMATON CONSTRUCTION AND SELECTION.


make-finite-state-automaton


Form
(make-finite-state-automaton start-state accept-state-list transitions [given-symbol-map])

Description
Make a finite state automaton with a given start-state, a list of accept states, and a set of transitions - a list. The optional parameter is a symbol map. In case it is passed, use this as symbol map for the resulting automaton, and do not in this case compact the transitions. In normal use, do not pass any such symbol map. The function make-finite-state-automaton will make the symbol map for you.

Parameters
start-stateThe start state of the automaton - an integer
accept-state-listThe list of accepting states - a list of integers
transitionsA list of transitions. Transitions are made by the function make-automaton-transition
given-symbol-mapA symbol map - a sorted vector - ala an association list that maps real input symbols to terse symbols

Returns
Returns a self-contained list structure that represents the final state automaton.


start-state-of-finite-state-automaton


Form
(start-state-of-finite-state-automaton aut)

Description
Return the start state of an automaton.


final-states-of-finite-state-automaton


Form
(final-states-of-finite-state-automaton aut)

Description
Return the list of final states of an automaton.


transitions-of-finite-state-automaton


Form
(transitions-of-finite-state-automaton aut)

Description
Return the transitions - a sorted vector - of an automaton.


transition-list-of-finite-state-automaton


Form
(transition-list-of-finite-state-automaton aut)

Description
Return the transitions - as a list - of an automaton.


symbol-map-of-finite-state-automaton


Form
(symbol-map-of-finite-state-automaton aut)

Description
Return the symbol map of an automaton. The symbol is an internal device which maps real input symbol to terse internal input symbols (for the sake of compact automaton representation).


 

2.   STATE AND TRANSITION PREDICATES.


state-equal?


Form
(state-equal state1 state2).

Description
The equality used for states in a final state automaton. Normally, the states are integers.


state-leq?


Form
(state-leq? state1 state2)

Description
A leq? function on states. The function is used to normalize subset states in the subset construction.


state-lt?


Form
(state-lt state1 state2)

Description
A less than function on states.


transition-leq?


Form
(transition-leq? trans1 trans2)

Description
A leq? function on transitions. The function is used for binary search among transitions for efficient lookup.


symbol-equal?


Form
(symbol-equal? sym1 sym2).

Description
The equality used for symbols in a final state automaton. Normally final state automaton symbols are Scheme symbols.


 

3.   TRANSITIONS


make-automaton-transition


Form
(make-automaton-transition in-state symbol out-state)

Description
Make a final state transition


from-state-of-transition


Form
(from-state-of-transition trans)

Description
Return the from-state of the transition.


symbol-of-transition


Form
(symbol-of-transition trans)

Description
Return the symbol of the transtion.


to-state-of-transition


Form
(to-state-of-transition trans)

Description
Return the to-state of the transition.


epsilon-symbol


Form
epsilon-symbol

Description
The denotation for the empty symbol.


epsilon-symbol?


Form
(epsilon-symbol? s)

Description
Is the symbol s an epsilon symbol?


epsilon-transition?


Form
(epsilon-transition? trans)

Description
Is the transition trans an epsilon transition?


 

4.   ACCEPTANCE PREDICATE.


automaton-accepts?


Form
(automaton-accepts? automaton symbol-list)

Description
Does automaton accepts the input symbol-list. This predicate should only be used if automaton is a DFA. If a NFA, first use the function subset-construction to construct a DFA from it. This function outputs either #t of #f.


 

5.   DFA CONSTRUCTION FROM NFA.
Construction of deterministic final automaton af non-deterministic final state automaton.


subset-construction


Form
(subset-construction nfa [support-epsilon-moves?])

Description
Return an equivalent DFA from the non-deterministic NFA passed as first parameter.

Parameters
nfaA non-deterministic final state automaton
support-epsilon-moves?A boolean parameter, defaulted to #f, which makes it possible to carry out the construction with epsilon moves in nfa


Generated: May 24, 2003, 13:23:13
This documentation has been extracted automatically from the Scheme source file by means of the Schemedoc tool