Tue, 08 Apr 2014 17:37:03 -0400

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

Re: NFA with non-deterministic outputs wyse03br@gmail.com (2014-09-09) |

From: | George Neuner <gneuner2@comcast.net> |

Newsgroups: | comp.compilers |

Date: | Tue, 08 Apr 2014 17:37:03 -0400 |

Organization: | A noiseless patient Spider |

References: | 14-04-004 |

Keywords: | lex, theory |

Posted-Date: | 10 Apr 2014 10:20:24 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.