Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #1217

Re: NFA with non-deterministic outputs

Show key headers only | View raw

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]

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

NFA with non-deterministic outputs wyse03br@gmail.com - 2014-04-07 12:17 -0700
  Re: NFA with non-deterministic outputs George Neuner <gneuner2@comcast.net> - 2014-04-08 17:37 -0400
  Re: NFA with non-deterministic outputs federation2005@netzero.com - 2014-04-13 11:51 -0700
    Re: NFA with non-deterministic outputs Kaz Kylheku <kaz@kylheku.com> - 2014-04-14 04:34 +0000
    Re: NFA with non-deterministic outputs wyse03br@gmail.com - 2014-09-09 14:26 -0700
      Re: NFA with non-deterministic outputs federation2005@netzero.com - 2014-10-20 15:18 -0700

csiph-web