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]>

Short Description

Why?

Author

License