From rbotting@wiley.csusb.edu Wed Jul 20 20:00 PDT 1994
Return-Path:
Received: from wiley.csusb.edu by silicon.csci.csusb.edu (5.0/SMI-SVR4)
id AA00351; Wed, 20 Jul 94 20:00:25 PDT
Received: by wiley.csusb.edu (5.67a/1.34)
id AA09485; Wed, 20 Jul 1994 19:59:34 -0700
Date: Wed, 20 Jul 1994 19:59:34 -0700
From: rbotting@wiley.csusb.edu ("Dr. Richard Botting")
Message-Id: <199407210259.AA09485@wiley.csusb.edu>
To: dick@silicon.csci.csusb.edu
Subject: (fwd) Re: A playground for regular languages
Newsgroups: comp.theory
Content-Type: text
Content-Length: 5112
Status: R
Newsgroups: comp.theory
Path: csus.edu!csusac!charnel.ecst.csuchico.edu!psgrain!rainrgnews0!pacifier!news.alpha.net!MathWorks.Com!europa.eng.gtefsd.com!howland.reston.ans.net!newsserver.jvnc.net!stevens-tech.edu!news
From: sutner@kleene.stevens-tech.edu (Klaus Sutner)
Subject: Re: A playground for regular languages
Message-ID: <1994Jul19.223903.27020@dmi.stevens-tech.edu>
Sender: news@dmi.stevens-tech.edu (USENET News System)
Organization: Stevens Institute Of Technology
References: <30g4u3$ge0@newshost.uni-koblenz.de>
Date: Tue, 19 Jul 1994 22:39:03 GMT
Lines: 137
This was originally meant for comp.theory.cell-automata, but
someone here might also be interested.
--------------------------------------------------------------
Some time ago, someone was looking for a "playground for regular
languages" on this group. For those of you who have access to
Mathematica, such a playground exists. It is called `automata' and
consists of a lot of Mathematica code, a number of notebooks, and
external code for critical algorithms. The package is available from
Mathsource (mathsource@wri.com). A more recent and expanded
version--if slightly less stable--is available by anonymous ftp from
menger.eecs.stevens-tech.edu (155.246.89.1)
see directory pub/sutner/automata
The package contains some stand-alone code that can be used without
Mathematica, but is rather limited in its capacity.
The crucial algorithms in the package are implemented in C code. This
makes it possible to build machines with tens of thousands of states
(if you have lots of RAM) and compute fairly large syntactic semigroups.
All the algorithms are also implemented directly in Mathematica, but, of
course, the size limits there are quite a bit lower and things slow down
significantly.
Since linear cellular automata can be construed as semiautomata,
the `automata' code can also be used to experiment with CAs.
For example, one can determine whether the global map of the CA is
injective, open or surjective. One can also compute the Welch indices
of surjective rules and invert injective rules.
Below is a sample session in `automata', using Jacobson's emacs frontend
for Mathematica. Notebooks would be more spectacular, but some of you
might not be able to view them.
Klaus Sutner
sutner@aiki.stevens-tech.edu
------------------------------------------------------------------
First, construct two FSMs. The first is a DFA that accepts all
words over alphabet {a,b} that contain 3 a's, the second is an FA
which accepts all words w such that w[-5] = b.
In[17]:= m1 = CounterDFA[ a, 3, {a,b} ]
Out[17]= DFA[5, {a, b}, {{2, 3, 4, 5, 5}, {1, 2, 3, 4, 5}}, 1, {4}]
In[18]:= m2 = IthSymbolFA[ b, -5, {a,b} ]
Out[18]= FA[6, {a, b}, {{1, 1, 1}, {1, 2, 1}, {1, 2, 2}, {2, 1, 3},
> {2, 2, 3}, {3, 1, 4}, {3, 2, 4}, {4, 1, 5}, {4, 2, 5}, {5, 1, 6},
> {5, 2, 6}}, {1}, {6}]
Now for their intersection and the minimal automaton (only the size is
displayed, in order not to waste an electronic tree).
In[19]:= mm = IntersectionFA[ m1, m2 ]; Size[mm]
Out[19]= 30
In[20]:= mmm = MinimizeFA[ mm ]; Size[mmm]
Out[20]= 57
Check correctnes by generating a small part of the acceptance language:
In[16]:= LanguageFA[ mm, -7 ] // LF
Out[16]= 0: {}
1: {}
2: {}
3: {}
4: {}
5: {baaab, baaba, babaa, bbaaa}
6: {abaabb, ababab, ababba, abbaab, abbaba, abbbaa, bbaaab,
> bbaaba, bbabaa, bbbaaa}
7: {aababbb, aabbabb, aabbbab, aabbbba, abbaabb, abbabab,
> abbabba, abbbaab, abbbaba, abbbbaa, babaabb, bababab,
> bababba, babbaab, babbaba, babbbaa, bbbaaab, bbbaaba,
> bbbabaa, bbbbaaa}
Perhaps of greater interest to this news group is the connection between
linear CAs and semiautomata. First, we construct an additive binary CA of
width 4. The result "2" in ClassifyCA below means: open but not
injective.
In[21]:= C = PolynomialToCA[ x1 + x2 + x4, 4 ]
Out[21]= CA[42330, 4, -2]
In[22]:= ClassifyCA[ C ]
Out[22]= 2
Hence C must be surjective, which we can also test by computing the
minimal DFA (a method that amounts to computational suicide in general).
In[24]:= C // ToSA // MinimizeFA // Size
Out[24]= 1
More interestingly, here are the Welch indices of C.
In[25]:= C // WelchCA
Out[25]= {1, 8, 1}
In other words: the semiautomaton associated with C is bideterministic
(a permutation automaton) and every configuration has exactly 8
predecessors.
Exercise
========
Explain the following (hint: on the server mentioned above, there is a
paper that might be helpful).
In[26]:= CA[42331, 4, -2] // ToSA // MinimizeFA // Size
Out[26]= 256
--
rbotting@wiley.csusb.edu.
rbotting::=`Dr. Richard J. Botting`, wiley::=`Faculty EMail System`,
csusb::=`California State University, San Bernardino, CA 92407, USA`.
Aka::=`dick@silicon.csci.csusb.edu`.
Disclaimer::=`CSUSB may or may not agree with this message`.
Copywrite(1994)::=`Copy and use as you wish, as long as you include this
copywrite message and signature`.