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

Groups > comp.compilers > #1211 > unrolled thread

NFA with non-deterministic outputs

Back to article view | Back to comp.compilers

Contents

  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

#1211 — NFA with non-deterministic outputs

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.

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.

So, here are the questions:

- is there any example or reference on NFAs issuing non-deterministic outputs?
It does not need to be a detailed one with all all therorems proved, just the
main concepts

- 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

- is there any reference of multiple NFAs cooperating? I'm particularly
concerned about inconsistencies between 2 NFAs. For instance, assuming that
NFA0 has a state Sx where an input a can move to Sy or Sz; and NFA1 has a
state Si that same input a can move to Sj or Sk; suppose that must be a
coherence between the non-determinism of both NFAs, such as Sx->Sy in NFA0
implies in Si->Sj in NFA1. How to model this to assure coherence between
NFAs?

Tks

[toc] | [next] | [standalone]

#1213

On Mon, 7 Apr 2014 12:17:44 -0700 (PDT), wyse03br@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.
>
>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.

NFA can model any kind of finite state machine.

>So, here are the questions:
>
>- is there any example or reference on NFAs issuing non-deterministic outputs?
>It does not need to be a detailed one with all all therorems proved, just the
>main concepts

State transitions [the edges in the graph] are directional and
represent outputs that also are inputs to other states.  A transition
can represent anything - not simply "acceptance" - and can represent
"transmission" of data between states.  Taking an outgoing transition
represents being in [acceptance of] the *source* state - entry into
the target state remains speculative until it evaluates and accepts
(or rejects) its input.


>- 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

You maybe could hack up something using a lexer tool, but it likely
would be more pain than it's worth ... you really are better off using
a more generalized FSM tool.

A better place to ask would be comp.arch.embedded.


>- is there any reference of multiple NFAs cooperating? I'm particularly
>concerned about inconsistencies between 2 NFAs. For instance, assuming that
>NFA0 has a state Sx where an input a can move to Sy or Sz; and NFA1 has a
>state Si that same input a can move to Sj or Sk; suppose that must be a
>coherence between the non-determinism of both NFAs, such as Sx->Sy in NFA0
>implies in Si->Sj in NFA1. How to model this to assure coherence between
>NFAs?

Unfortunately, the only decent references I know of are CS text books
on finite automata.  Googling for "nondeterministic finite automata
coordination" might turn up something interesting.

Just as 2 FSM can be combined into 1 bigger FSM, so can 2 NFAs can be
combined into 1 NFA.  The best way (if possible) would be to fold Sx
and Si into a single state that outputs coordinated transitions.  If
the NFA must remain separate, then Sx and Si somehow must communicate
[message passing] to coordinate their activities.

In short, everything you already know about FSM also applies to NFA.

George

[toc] | [prev] | [next] | [standalone]

#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]

[toc] | [prev] | [next] | [standalone]

#1220

On 2014-04-13, federation2005@netzero.com <federation2005@netzero.com> wrote:
> So, no. NFA's are not the appropriate model to use here. Rather, one would use
> a non-deterministic FSM (finite state machine).

"FA" stands for "finite automaton", which is a synonym of FSM, "finite state machine".

There is no difference between "NFA" and "non-deterministic FSM".

[toc] | [prev] | [next] | [standalone]

#1372

Going back to this topic, tks for the updates. The non-deterministic
FSM seems to be the best approach indeed. Your rex tool seems to be
suited to my needs, but I couldn't find it anywhere either. Do you
suggest anything else?

Rgds

On Sunday, April 13, 2014 3:51:36 PM UTC-3, federat...@netzero.com wrote:
> 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). ...

[toc] | [prev] | [next] | [standalone]

#1388

On Tuesday, September 9, 2014 4:26:07 PM UTC-5, wyse...@gmail.com wrote:
> Going back to this topic, tks for the updates. The non-deterministic
> FSM seems to be the best approach indeed. Your rex tool seems to be
> suited to my needs, but I couldn't find it anywhere either. Do you
> suggest anything else?

To follow up on my earlier reply -- which I didn't finish -- I spent some time
rewriting and adding a little to the source for the code. Given time I'll put
up a version maybe on SourceForge or maybe as a PDF embedded in the written
narrative over on Scribd. (Or maybe even post the source here, later.)

A description follows below. As for the original query -- relating this to the
code described below -- if you're seeking to process FSM's (with *both* input
and output), the same reductions apply ... initially ... as what the software
will do. In general, you'll get a matrix system of the form
   S -> i q
   q -> f | X q | Y q
where q and f are column n-vectors (a being 0/1 valued), i a row n-vector
(also 0/1 valued), X and Y are n x n matrices of the form X = sum (x X_x)
summed over all input symbols x, with each X_x being 0-1 valued and Y defined
similarly sum (y Y_y) summed over all output symbols y. The resulting subset
would just be
   S = i (X | Y)* f.

In general, you can NOT get a deterministic FSM out of this, because there may
be multiple outputs for a given input. However, what you *can* do is write
down something in "quasi-deterministic" form
   q -> Y* f | Y* X q = Y* f | (sum_x x Y* X_x) q
This associates a regular subset of the outputs Y* f with the end symbol, and
regular subsets Y* X_x with each input symbol x in matrix for.

This reduces the above expression to the form
   S = i (sum_x Y* X_x x)* Y* f

The result is an idempotent power series over the monoid of input words. If
you had a word x_0 x_1 ... x_m, the outputs would be given by the regular
expression
   i Y* X_{x_0} Y* X_{x_1} ... Y* X_{x_m} Y* f.

However, to obtain in explicit form would require a routine for converting
back all the Y expressions back from matrix or automata form to regular
expression form. I haven't written any FSA -> RE converter. The complexity is
n^3 for such a reduction (although it may be of smaller complexity if the
substitution operator -- described below -- is used).

These are the routines I have:
FSC.c (about 150 lines) is a finite state classifier. It takes input like
this
0a
0ba
1bb
0aab
where the first character on each line indicates the word class and produces
the smallest FSAs that correctly classifies the given examples.

REX.c (about 650 lines) is functionally superior to GREP -- it handles Boolean
operators as well as the interleave operator, in additional to the
Kleene-algebraic regular expression operators.

NFA.c and DFA.c are respectively about 350 and 450 lines and processe regular
expressions in the format:

Ex -> '(' Ex ')'
Ex -> '[' Ex ']'
Ex -> Ex p
Ex -> Ex [i] Ex,
Ex -> x '=' Ex ',' Ex,	// substitution operator
Ex -> Name/Identifier,	// a C-identifier or "..." quoted-name.
Ex -> Literal Constant,	// '0' or '1'

The postfix operators (p) are the Kleene star "*", the 1-or-more "+", the
0-or-1 "?" (so that E? is synonymous with [E]).

The infix operators are "|" and the (empty) operator for concatenation. For
DFA, they also include "&" for intersection, "-" for set subtraction, "^" for
interleave.

The substitution operator (x = A, B) has local scope, therefore,
	(x = y y, x a) | b x
means y y a | b x, not y y a | b y y.

For instance, the input,
S = 0,
S = [S ^ (a b)*],
S = [S ^ (a b)*],
S = [S ^ (a b)*],
S = [S ^ (a b)*],
S
is a regular expression for handling the context-free subset given by the
grammar S -> 1 | a S b S up to 4 levels of recursion, while this one
S = 0,
S = [S ^ (a b c)*],
S = [S ^ (a b c)*],
S = [S ^ (a b c)*],
S = [S ^ (a b c)*],
S
is a 4-level approximation for the language given by S -> 1 | S ^ (a b c)*,
which is context-sensitive, but not context-free.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compilers

csiph-web