Registered: Jun 2004
Posts: 1

Hello - this is my first post so I would like to say hello to all of you.

I'm implementing a algorithm that returns a transition minimal automaton from any given automaton: this being achieved by adding epsilon transitions between existing transitions of the original automata if and only iff the language of this new automaton is the same as the original automaton. Then by analysing similarities in the adjacency matrix (follow-relation really) we find out which transitions are equivalent, and retain just one of each equivalence class to result in a reduced transition minimal automaton.

This algorithm was presented by Sebastian John and can be found here:
http://user.cs.tu-berlin.de/~sebc/T...22-SJohn.pdf.gz

I'm fairly new in this field and I am faced with the problem of testing the equality of the languages of two given automata.

Does anybody know of a way to test this?

Appologies for any obvious ignorances I have -

Thanks for your time and help

Edd.

Report this post to a moderator | IP: Logged

Registered: Feb 2004
Posts: 551

Hi Edward,

Grammar induction is always hard. In my own explorations
of the subject I eventually found it necessary to abandon
all cleverness and proceed empirically. In doing this we
assume that we have a grammar-unknown source generating
a formal language L c !A!*, and the best that we can do
by way of capturing its regularities on the fly, that is,
after the fashion of a realtime data stream, is to form
the finite state transition tree for the language L_t
that approximates L up to the date t. One then has
a data basis for comparing language sources based
on their finite state approximations.

One component of a program that I wrote in the 80's
implements this strategy for 2-level formal languages,
that is, formal languages that have a "lexical" level
for the "words" and a "literal" level for the "phrases".

I am somewhat tardily documenting this work,
for example, at the following list location:

http://stderr.org/pipermail/inquiry...thread.html#102

Have had it on my slate to try and see if this program
could be redone in Mathematica, but may not get around
to it any time soon. Always interested in talking to
anybody who wants to try it, though.

Jon Awbrey

Report this post to a moderator | IP: Logged

Registered: Oct 2003
Posts: 38

Hello Edward,

I dont have a direct reply to your answer. Here are some pointers to mathematica packages that might be useful however --

http://library.wolfram.com/infocenter/MathSource/892/

http://www-2.cs.cmu.edu/~sutner/automata.html

__________________
Everything is an expression.

Report this post to a moderator | IP: Logged