MOTION-GRAMMAR-KIT - Formal Language Tools for Robots



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



  1. Download
  2. The MOTION-GRAMMAR-KIT dictionary
    1. dfa-eq
    2. dfa-p
    3. fa->regex
    4. fa->right-regular-grammar
    5. fa-canonicalize
    6. fa-complement
    7. fa-dot
    8. fa-empty-p
    9. fa-equiv
    10. fa-intersection
    11. fa-union
    12. fa-universal-p
    13. finite-automaton
    14. grammar->cnf
    15. grammar->fa
    16. grammar->pda
    17. grammar->right-regular
    18. grammar-remove-useless
    19. make-empty-fa
    20. make-fa
    21. make-pda
    22. make-universal-fa
    23. nfa->dfa
    24. pda-dot
    25. pda-fa-intersection
    26. pda-reachability-automaton
    27. pushdown-automaton
    28. regex->dfa
    29. regex->nfa
    30. regex-sweeten
  3. Acknowledgements



MOTION-GRAMMAR-KIT together with this documentation can be downloaded from Detailed install instructions are included with the source.


dfa-eq a bresult

Check equivalence up to state names of DFAs

dfa-p faresult

True if FA is deterministic

fa->regex faresult

Convert FA to a regular expression.

fa->right-regular-grammar faresult

Convert FA to a right-regular grammar.

fa-canonicalize faresult

Return a canonical representation of FA. Minimize the state of FA and rename state variables.

fa-complement fa &optional terminalsresult

Return the complement of FA. This is the finite-automaton that accepts all strings NOT in FA.

fa-dot fa &key output font-size accept-shaperesult

Generate Graphviz output for FA. FA: finite automaton. OUTPUT: output file, type determined by suffix (png,pdf,eps).

fa-empty-p faresult

Does FA include no strings?

fa-equiv a bresult

Check if two FAs recognize the same language.

fa-intersection fa1 fa2result

Intersection of FA1 and FA2

fa-union fa1 fa2 &optional uniqueresult

Union of finite automata FA1 and FA2.

fa-universal-p fa &optional terminalsresult

Does FA recognize all strings over TERMINALS?

[Standard class]

A Finite Automaton.

grammar->cnf grammarresult

Convert grammar to Chomsky Normal Form

grammar->fa grammar &key acceptresult

Convert grammar to a finite automata. GRAMMAR: a right regular grammar (or something close to right regular) RESULT: a finite automaton

grammar->pda grammarresult

Convert GRAMMAR to a PDA.

grammar->right-regular grammarresult

Attempt to convert this grammar to right-regular form. Please note that this operation is not always possible.

grammar-remove-useless grammar &optional terminals nonterminalsresult

Remove 'useless' symbols from GRAMMAR.

make-empty-fa terminalsresult

Create an FA including no strings.

make-fa edges start acceptresult

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.

make-pda edges start acceptresult

Make a pushdown automaton.

make-universal-fa terminalsresult

Create an FA recognizing all strings over TERMINALS.

nfa->dfa nfaresult

Convert an NFA to a DFA

pda-dot pda &key output font-sizeresult

Generate Graphviz output for PDA.

pda-fa-intersection pda fa &optional gensymresult

Compute the intersection of PDA and DFA. RESULT: a pda

pda-reachability-automaton pdaresult

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]

A Pushdown Automaton.

regex->dfa regexresult

Convert a regular expression to a DFA.

regex->nfa regexresult

Convert a regular expression to an NFA.

regex-sweeten regex terminals &key concatenate-stringsresult

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.