NFA with non-deterministic outputs

Path	csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!news.linkpendium.com!news.linkpendium.com!news.iecc.com!.POSTED!nerds-end
From	wyse03br@gmail.com
Newsgroups	comp.compilers
Subject	NFA with non-deterministic outputs
Date	Mon, 7 Apr 2014 12:17:44 -0700 (PDT)
Organization	Compilers Central
Lines	28
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<14-04-004@comp.compilers> (permalink)
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 1396928390 36698 2001:470:1f07:1126:0:676f:7373:6970 (8 Apr 2014 03:39:50 GMT)
X-Complaints-To	abuse@iecc.com
NNTP-Posting-Date	Tue, 8 Apr 2014 03:39:50 +0000 (UTC)
Keywords	lex, question
Posted-Date	07 Apr 2014 23:39:50 EDT
X-submission-address	compilers@iecc.com
X-moderator-address	compilers-request@iecc.com
X-FAQ-and-archives	http://compilers.iecc.com
Xref	csiph.com comp.compilers:1211

Show key headers only | View raw

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

Back to comp.compilers | Previous | Next — 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