Re: NFA with non-deterministic outputs

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]

Return to the comp.compilers page.
Search the comp.compilers archives again.