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

Groups > comp.arch.embedded > #25819

Re: Do you use FSMs or HSMs?

Show key headers only | View raw

George Neuner wrote:
> On Mon, 6 Feb 2017 23:36:01 -0600, Les Cargill
> <lcargill99@comcast.com> wrote:
>
>> Clifford Heath wrote:
>>
>>> Lex is a language for describing a regular expression,
>>> which it implements by turning it *into* an FSA.
>>>
>>> You don't need yacc to parse FP numbers. Such parsers
>>> are for handling languages that require unbounded state,
>>> not finite state.
>>
>> Just to be pedantic :), it's deterministic vs. non deterministic FA.
>> Deterministic FA are equivalent to regular expressions. NFA
>> are not, and very often, NFA are what we use for program control flow.
>
> Every NFA is equivalent to some DFA, and either can be mechanically
> translated into the other.  However the DFA version, in general, will
> have many more states: in the (theoretical) worst case, equal to the
> size of the power set of states in the NFA.
>

I've had perfectly good NFA deployed that I would hate
to have to translate into a regexp :)

As  a practical matter ( and as you note ) , there is a very
significant tactical difference.

> But such explosive growth is very rare.  In practice, the majority of
> elements in the power set of NFA states will represent either unwanted
> or redundant operations.
>
>
>>> I'm also enthusiastic in using FSAs where appropriate,
>>> but a lot of problems I face require unbounded state.
>>
>> This is where NFA shine - they're less formal than DFA.
>
> Not "less formal" per se if you are concerned about correctness.
> However, in general, NFA are easier to specify and to understand.
>

That's the key. As you say - there may be a (small) price in
the ability to demonstrate correctness.

The principal advantage is the ability to generate
nearly exhaustive test suites for them. It at least becomes a matter of 
exploiting combinators.

> Any particular state of the equivalent DFA may be simultaneously
> representing multiple states of the NFA.  Consequently, the
> transition/acceptance rules in the DFA may be extremely complex -
> perhaps even incomprehensible to mere mortals.
>
>
> George
>

-- 
Les Cargill

Back to comp.arch.embedded | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Do you use FSMs or HSMs? pozz <pozzugno@gmail.com> - 2017-02-06 10:43 +0100
  Re: Do you use FSMs or HSMs? Don Y <blockedofcourse@foo.invalid> - 2017-02-06 03:20 -0700
  Re: Do you use FSMs or HSMs? Dave Nadler <drn@nadler.com> - 2017-02-06 06:38 -0800
  Re: Do you use FSMs or HSMs? "QL" <80499@EmbeddedRelated> - 2017-02-06 08:56 -0600
    Re: Do you use FSMs or HSMs? Don Y <blockedofcourse@foo.invalid> - 2017-02-06 12:13 -0700
    Re: Do you use FSMs or HSMs? jim.brakefield@ieee.org - 2017-02-06 16:52 -0800
      Re: Do you use FSMs or HSMs? Don Y <blockedofcourse@foo.invalid> - 2017-02-06 18:11 -0700
      Re: Do you use FSMs or HSMs? Les Cargill <lcargill99@comcast.com> - 2017-02-06 23:32 -0600
    Re: Do you use FSMs or HSMs? pozz <pozzugno@gmail.com> - 2017-02-07 10:39 +0100
  Re: Do you use FSMs or HSMs? John Speth <johnspeth@yahoo.com> - 2017-02-06 09:17 -0800
    Re: Do you use FSMs or HSMs? Tom Gardner <spamjunk@blueyonder.co.uk> - 2017-02-06 18:03 +0000
      Re: Do you use FSMs or HSMs? Don Y <blockedofcourse@foo.invalid> - 2017-02-06 11:56 -0700
        Re: Do you use FSMs or HSMs? Tom Gardner <spamjunk@blueyonder.co.uk> - 2017-02-06 20:34 +0000
          Re: Do you use FSMs or HSMs? Don Y <blockedofcourse@foo.invalid> - 2017-02-06 14:19 -0700
            Re: Do you use FSMs or HSMs? Tom Gardner <spamjunk@blueyonder.co.uk> - 2017-02-06 22:12 +0000
              Re: Do you use FSMs or HSMs? Don Y <blockedofcourse@foo.invalid> - 2017-02-06 15:29 -0700
              Re: Do you use FSMs or HSMs? Phil Hobbs <pcdhSpamMeSenseless@electrooptical.net> - 2017-02-08 12:15 -0500
                Re: Do you use FSMs or HSMs? Tom Gardner <spamjunk@blueyonder.co.uk> - 2017-02-08 23:52 +0000
                Re: Do you use FSMs or HSMs? Phil Hobbs <pcdhSpamMeSenseless@electrooptical.net> - 2017-02-08 19:59 -0500
              Re: Do you use FSMs or HSMs? Steve Watt <steve.removethis@Watt.COM> - 2017-02-17 00:30 +0000
                Re: Do you use FSMs or HSMs? Tom Gardner <spamjunk@blueyonder.co.uk> - 2017-02-17 00:44 +0000
            Re: Do you use FSMs or HSMs? Clifford Heath <no.spam@please.net> - 2017-02-07 10:12 +1100
              Re: Do you use FSMs or HSMs? Les Cargill <lcargill99@comcast.com> - 2017-02-06 23:36 -0600
                Re: Do you use FSMs or HSMs? George Neuner <gneuner2@comcast.net> - 2017-02-07 03:15 -0500
                Re: Do you use FSMs or HSMs? Les Cargill <lcargill99@comcast.com> - 2017-02-10 17:41 -0600
                Re: Do you use FSMs or HSMs? Clifford Heath <no.spam@please.net> - 2017-02-07 19:56 +1100
                Re: Do you use FSMs or HSMs? Paul Rubin <no.email@nospam.invalid> - 2017-02-07 01:30 -0800
                Re: Do you use FSMs or HSMs? Clifford Heath <no.spam@please.net> - 2017-02-07 20:42 +1100
                Re: Do you use FSMs or HSMs? Paul Rubin <no.email@nospam.invalid> - 2017-02-07 02:46 -0800
                Re: Do you use FSMs or HSMs? Clifford Heath <no.spam@please.net> - 2017-02-08 00:27 +1100
  Re: Do you use FSMs or HSMs? Paul Rubin <no.email@nospam.invalid> - 2017-02-06 18:35 -0800
    Re: Do you use FSMs or HSMs? Don Y <blockedofcourse@foo.invalid> - 2017-02-06 21:50 -0700
    Re: Do you use FSMs or HSMs? Les Cargill <lcargill99@comcast.com> - 2017-02-06 23:39 -0600
      Re: Do you use FSMs or HSMs? Paul Rubin <no.email@nospam.invalid> - 2017-02-06 23:20 -0800
        Re: Do you use FSMs or HSMs? Les Cargill <lcargill99@comcast.com> - 2017-02-10 17:47 -0600
          Re: Do you use FSMs or HSMs? Paul Rubin <no.email@nospam.invalid> - 2017-02-10 16:11 -0800
            Re: Do you use FSMs or HSMs? Les Cargill <lcargill99@comcast.com> - 2017-02-11 15:43 -0600
  Re: Do you use FSMs or HSMs? Les Cargill <lcargill99@comcast.com> - 2017-02-06 23:24 -0600

csiph-web