R egular L anguages and S yntactic M onoids
Short Description
This is a ruby implementation of three concepts:
- Deterministic Finite Automata (DFA)
- Regular Expressions (in the sense of theoretical computer sience)
- Monoids (an algebraic construct)
It is possible to convert
Monoid -> DFA
DFA -> RegExp
RegExp -> DFA
DFA -> Monoid
Why?
In formal language theory, a language is a subset of the free monoid Sigma*, where Sigma is a finite set (the alphabet). An algebraic approach to study the properties of formal languages is given by the definition of the syntactic Monoid of a language.
A major result in this area is, that a language is regular iff its syntatcic monoid is finite. It is also known, that a language with a finite aperiodic monoid as syntactic monoid is star free (i.e. the corresponding regexp can be written without the Kleene-star.)
This code is written as an attemp to simplify the further study of finite monoids.
Author
asmodis <[email protected]>
License
GPL v3 Copyright 2008 Gunther Diemant