Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!news.linkpendium.com!news.linkpendium.com!news.iecc.com!.POSTED!nerds-end From: George Neuner Newsgroups: comp.compilers Subject: Re: NFA with non-deterministic outputs Date: Tue, 08 Apr 2014 17:37:03 -0400 Organization: A noiseless patient Spider Lines: 60 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <14-04-006@comp.compilers> References: <14-04-004@comp.compilers> NNTP-Posting-Host: news.iecc.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Trace: miucha.iecc.com 1397139624 67101 2001:470:1f07:1126:0:676f:7373:6970 (10 Apr 2014 14:20:24 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Thu, 10 Apr 2014 14:20:24 +0000 (UTC) Keywords: lex, theory Posted-Date: 10 Apr 2014 10:20:24 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: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