wolframscience.com

A New Kind of Science: The NKS Forum : Powered by vBulletin version 2.3.0 A New Kind of Science: The NKS Forum > NKS Way of Thinking > Finding out an automata's language
  Last Thread   Next Thread
Author
Thread Post New Thread    Post A Reply
Edward Turner
Southampton University
United Kingdom

Registered: Jun 2004
Posts: 1

Finding out an automata's language

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

Old Post 06-11-2004 10:37 AM
Edward Turner is offline Click Here to See the Profile for Edward Turner Click here to Send Edward Turner a Private Message Click Here to Email Edward Turner Visit Edward Turner's homepage! Edit/Delete Message Reply w/Quote
Jon Awbrey


Registered: Feb 2004
Posts: 558

Finding Out A Language's Automata

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

Old Post 06-11-2004 01:52 PM
Jon Awbrey is offline Click Here to See the Profile for Jon Awbrey Click here to Send Jon Awbrey a Private Message Visit Jon Awbrey's homepage! Edit/Delete Message Reply w/Quote
Kovas Boguta
Wolfram Science Group

Registered: Oct 2003
Posts: 38

some pointers

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

Old Post 06-11-2004 06:53 PM
Kovas Boguta is offline Click Here to See the Profile for Kovas Boguta Click here to Send Kovas Boguta a Private Message Visit Kovas Boguta's homepage! Edit/Delete Message Reply w/Quote
Post New Thread    Post A Reply
  Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread


 

wolframscience.com  |  wolfram atlas  |  NKS online  |  Wolfram|Alpha  |  Wolfram Science Summer School  |  web resources  |  contact us

Forum Sponsored by Wolfram Research

© 2004-14 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives