Sun, 13 Apr 2014 11:51:36 -0700 (PDT)

Related articles |
---|

NFA with non-deterministic outputs wyse03br@gmail.com (2014-04-07) |

Re: NFA with non-deterministic outputs gneuner2@comcast.net (George Neuner) (2014-04-08) |

Re: NFA with non-deterministic outputs federation2005@netzero.com (2014-04-13) |

Re: NFA with non-deterministic outputs kaz@kylheku.com (Kaz Kylheku) (2014-04-14) |

From: | federation2005@netzero.com |

Newsgroups: | comp.compilers |

Date: | Sun, 13 Apr 2014 11:51:36 -0700 (PDT) |

Organization: | Compilers Central |

References: | 14-04-004 |

Keywords: | lex, theory, comment |

Posted-Date: | 14 Apr 2014 00:25:55 EDT |

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]

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.