Generated: Monday, November 14, 2011, 09:18:17 Copyright © 2011 , Kurt NÝrmark The local LAML software home page

Reference Manual of the LAML Finite State Automaton library

Kurt NÝrmark © normark@cs.aau.dk Department of Computer Science, Aalborg University, Denmark.

LAML Source file: lib/final-state-automaton.scm

This is a Scheme library that support Finite 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-symbol epsilon-symbol The 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 finite 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 finite 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 finite 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-state The start state of the automaton - an integer
accept-state-list The list of accepting states - a list of integers
transitions A list of transitions. Transitions are made by the function make-automaton-transition
given-symbol-map A 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 finite state automaton.
See also Scheme source file make-finite-state-automaton

start-state-of-finite-state-automaton
Form (start-state-of-finite-state-automaton aut)
Description Return the start state of an automaton.
See also Scheme source file start-state-of-finite-state-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.
See also Scheme source file final-states-of-finite-state-automaton

transitions-of-finite-state-automaton
Form (transitions-of-finite-state-automaton aut)
Description Return the transitions - a sorted vector - of an automaton.
See also Scheme source file transitions-of-finite-state-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.
See also Scheme source file transition-list-of-finite-state-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).
See also Scheme source file symbol-map-of-finite-state-automaton


2 State and transition predicates.

state-equal?
Form (state-equal state1 state2).
Description The equality used for states in a finite state automaton. Normally, the states are integers.
See also Scheme source file state-equal?

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.
See also Scheme source file state-leq?

state-lt?
Form (state-lt state1 state2)
Description A less than function on states.
See also Scheme source file state-lt?

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.
See also Scheme source file transition-leq?

symbol-equal?
Form (symbol-equal? sym1 sym2).
Description The equality used for symbols in a finite state automaton. Normally finite state automaton symbols are Scheme symbols.
See also Scheme source file symbol-equal?


3 Transitions

make-automaton-transition
Form (make-automaton-transition in-state symbol out-state)
Description Make a finite state transition
See also Scheme source file make-automaton-transition

from-state-of-transition
Form (from-state-of-transition trans)
Description Return the from-state of the transition.
See also Scheme source file from-state-of-transition

symbol-of-transition
Form (symbol-of-transition trans)
Description Return the symbol of the transtion.
See also Scheme source file symbol-of-transition

to-state-of-transition
Form (to-state-of-transition trans)
Description Return the to-state of the transition.
See also Scheme source file to-state-of-transition

epsilon-symbol
Form epsilon-symbol
Description The denotation for the empty symbol.
See also Scheme source file epsilon-symbol

epsilon-symbol?
Form (epsilon-symbol? s)
Description Is the symbol s an epsilon symbol?
See also Scheme source file epsilon-symbol?

epsilon-transition?
Form (epsilon-transition? trans)
Description Is the transition trans an epsilon transition?
See also Scheme source file 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.
See also Scheme source file automaton-accepts?


5 DFA construction from NFA.
Construction of deterministic finite automaton af non-deterministic finite 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 nfa A non-deterministic finite 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
See also Scheme source file subset-construction

Generated: Monday, November 14, 2011, 09:18:18
Generated by LAML SchemeDoc using LAML Version 38.0 (November 14, 2011, full)