Abstract
This package provides a variety of functions for symbolic manipulation of formal language models. The code comes with a BSD-style license so you can basically do with it whatever you want.Repository: git clone https://github.com/golems/motion-grammar-kit
dfa-eq
dfa-p
fa->regex
fa->right-regular-grammar
fa-canonicalize
fa-complement
fa-dot
fa-empty-p
fa-equiv
fa-intersection
fa-union
fa-universal-p
finite-automaton
grammar->cnf
grammar->fa
grammar->pda
grammar->right-regular
grammar-remove-useless
make-empty-fa
make-fa
make-pda
make-universal-fa
nfa->dfa
pda-dot
pda-fa-intersection
pda-reachability-automaton
pushdown-automaton
regex->dfa
regex->nfa
regex-sweeten
[Function]
dfa-eq a b → result
Check equivalence up to state names of DFAs
[Function]
dfa-p fa → result
True if FA is deterministic
[Function]
fa->regex fa → result
Convert FA to a regular expression.
[Function]
fa->right-regular-grammar fa → result
Convert FA to a right-regular grammar.
[Function]
fa-canonicalize fa → result
Return a canonical representation of FA. Minimize the state of FA and rename state variables.
[Function]
fa-complement fa &optional terminals → result
Return the complement of FA. This is the finite-automaton that accepts all strings NOT in FA.
[Function]
fa-dot fa &key output font-size accept-shape → result
Generate Graphviz output for FA. FA: finite automaton. OUTPUT: output file, type determined by suffix (png,pdf,eps).
[Function]
fa-empty-p fa → result
Does FA include no strings?
[Function]
fa-equiv a b → result
Check if two FAs recognize the same language.
[Function]
fa-intersection fa1 fa2 → result
Intersection of FA1 and FA2
[Function]
fa-union fa1 fa2 &optional unique → result
Union of finite automata FA1 and FA2.
[Function]
fa-universal-p fa &optional terminals → result
Does FA recognize all strings over TERMINALS?
[Standard class]
finite-automaton
A Finite Automaton.
[Function]
grammar->cnf grammar → result
Convert grammar to Chomsky Normal Form
[Function]
grammar->fa grammar &key accept → result
Convert grammar to a finite automata. GRAMMAR: a right regular grammar (or something close to right regular) RESULT: a finite automaton
[Function]
grammar->pda grammar → result
Convert GRAMMAR to a PDA.
[Function]
grammar->right-regular grammar → result
Attempt to convert this grammar to right-regular form. Please note that this operation is not always possible.
[Function]
grammar-remove-useless grammar &optional terminals nonterminals → result
Remove 'useless' symbols from GRAMMAR.
[Function]
make-empty-fa terminals → result
Create an FA including no strings.
[Function]
make-fa edges start accept → result
Create a finite-automaton. EDGES: List of edges, each (list state-0 terminal state-1). START: The automaton start state. ACCEPT: Set of automaton accept states.
[Function]
make-pda edges start accept → result
Make a pushdown automaton.
[Function]
make-universal-fa terminals → result
Create an FA recognizing all strings over TERMINALS.
[Function]
nfa->dfa nfa → result
Convert an NFA to a DFA
[Function]
pda-dot pda &key output font-size → result
Generate Graphviz output for PDA.
[Function]
pda-fa-intersection pda fa &optional gensym → result
Compute the intersection of PDA and DFA. RESULT: a pda
[Function]
pda-reachability-automaton pda → result
Compute the reachability automaton for the PDA. This is an FA with the same control states as PDA and whose language defines the set of all stack contents possible at each control state.
[Standard class]
pushdown-automaton
A Pushdown Automaton.
[Function]
regex->dfa regex → result
Convert a regular expression to a DFA.
[Function]
regex->nfa regex → result
Convert a regular expression to an NFA.
[Function]
regex-sweeten regex terminals &key concatenate-strings → result
Apply some syntactic sugar to REGEX. Supports the following operators: :complement : match complement :not : any symbol except this :+ : A A* :. : match anything REGEX: An extended regular expression. TERMINALS: Set of all terminal symbols in the language.
This documentation was prepared with DOCUMENTATION-TEMPLATE.