Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!peer02.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!border3.nntp.dca.giganews.com!backlog3.nntp.dca3.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end
From: federation2005@netzero.com
Newsgroups: comp.compilers
Subject: Re: NFA with non-deterministic outputs
Date: Sun, 13 Apr 2014 11:51:36 -0700 (PDT)
Organization: Compilers Central
Lines: 85
Sender: news@iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <14-04-010@comp.compilers>
References: <14-04-004@comp.compilers>
NNTP-Posting-Host: news.iecc.com
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Trace: miucha.iecc.com 1397449555 78927 2001:470:1f07:1126:0:676f:7373:6970 (14 Apr 2014 04:25:55 GMT)
X-Complaints-To: abuse@iecc.com
NNTP-Posting-Date: Mon, 14 Apr 2014 04:25:55 +0000 (UTC)
Keywords: lex, theory, comment
Posted-Date: 14 Apr 2014 00:25:55 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
X-Original-Bytes: 5064
X-Received-Bytes: 5168
X-Received-Body-CRC: 2822443066
Xref: csiph.com comp.compilers:1217

On Monday, April 7, 2014 2:17:44 PM UTC-5, wyse...@gmail.com wrote:
> I need to model some inter-operating FSMs and due to the lack of
> details in their specification, modelling them as NFAs seems to be the
> best approach.

A finite automaton models a regular language -- technically: a rational subset
of a free monoid X*, where X is the underlying alphabet.

A "finite automaton with outputs" is a finite state *machine*, which models a
*rational transduction*, which is a rational subset of the product monoid X* x
Y*, where X and Y are the alphabets respectively for inputs and outputs.

So, no. NFA's are not the appropriate model to use here. Rather, one would use
a non-deterministic FSM (finite state machine).

Note, BTW, that unlike the case for NFA and DFA, where an NFA can be converted
to a DFA, there is no conversion from non-deterministic FSM to deterministic
FSM for the simple reason that one could have a rational subset of X* x Y*
which associates two or more words from Y* with a given word from X*. The
simplest example is with X = {a}, Y = {b,c} and the rational subset being
given by {(a,b),(a,c)} with the FSM:
   Start = [0]
   End = [1]
   Transitions: [0] -> a/b -> [1], [0] -> a/c -> [2].
(And *all* finite subsets of any monoid, including X* x Y*, are rational
subsets.)

> Getting more information about NFAs, it seems that they are mostly used as
> acceptors (no outputs besides accept or no-accept). But I need to model also
> their outputs (transducers?). Besides that, some of these outputs might be
> inputs for the other NFAs.

There is a distinction, that I'm not aware being clearly made anywhere in the
literature, between a "recognizer", "transducer" and "acceptor" ... along with
a "duality theorem" (that I've never seen published anywhere) and "equivalence
theorems" (likewise) of the following sort ... which can be stated in quite
general form for *arbitrary* monoids:

(1) Duality
A correspondence between a finite state machine A0 with input monoid M x N and
output monoid P, versus a finite state machine A1 with input monoid M and
output monoid N x P.

This reflects the "associator identity" ((M x N) x P = M x (N x P)) which is
generic to "monoidal" (or "tensor") categories.

The duality is the dual role played by the channel corresponding to N. For
both A0 and A1, M is an input channel, P an output channel, while N is a 2nd
input channel for A0, but a 2nd output channel for A1.

(2) Equivalences
Each recognizer for a monoid M is associated with a transducer M x 1 (defining
the trivial 1-element monoid 1 as {0}).

Each generator for a monoid N is associated with a transducer 1 x N.

These reflect the "unitor identities" (M x 1 = M and 1 x N = N) of a tensor
category.

With (2), you can convert between a generator and recognizer:
   M <-> M x 1 = (1 x M) x 1 = 1 x (M x 1) = 1 x M <-> M
and between a 2-channel generator, transducer and 2-channel recognizer:
   (M x N) x 1 = M x N = 1 x (M x N).
With (1) you can do the same
   M x N = 1 x (M x N) = (1 x M) x N = (M x 1) x N
 = M x (1 x N) = M x (N x 1) = (M x N) x 1.

(These chains of identities also figure prominently in the definition of
tensor categories.)

> So, here are the questions:
> - is there any tool that gets the description of a NFA (issuing outputs)
and
> translates it to a DFA (deterministic finite state machine), in a format
> simple to parse, to feed other tools

I'm not sure if it is still there, but my regex stuff found its way into the
comp.compilers archive in the 1990's under a subdirectory titled "rex". This
includes an algebraically grounded description of all the things you're asking
for, a program (NFA.c) for doing RegEx -> NFA, a program (DFA.c) for doing
RegEx -> DFA (in which the reg ex's may include boolean operations), and a
program REX for doing everything GREP does and more (boolean operations and
interleaves).
[I thought I still have everything that I put into the FTP archive,
but I don't have that. -John]