Re: Good resource for learning about implementing finite state automata in c++?

Path	csiph.com!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail
From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.programming
Subject	Re: Good resource for learning about implementing finite state automata in c++?
Date	Sun, 17 Jan 2016 00:07:04 +0000
Organization	A noiseless patient Spider
Lines	31
Message-ID	<871t9hgjbr.fsf@bsb.me.uk> (permalink)
References	<2810bf26-590f-43a5-af9e-a406433b6126@googlegroups.com>
Mime-Version	1.0
Content-Type	text/plain
Injection-Info	mx02.eternal-september.org; posting-host="017616aa25f81ec581c44d76d61ba2f3"; logging-data="30179"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18PcrYLAbUv/r//e7FLvg7Xiq8XiIsOLNw="
Cancel-Lock	sha1:FhC6aTHkMRFKzvyeBCVpzEFy4Tk= sha1:vDSEMREX8BZ0NR+dC9XbvyU+OHU=
X-BSB-Auth	1.26e8f4f57926a7855ba2.20160117000704GMT.871t9hgjbr.fsf@bsb.me.uk
Xref	csiph.com comp.programming:6223

Show key headers only | View raw

Paul <pepstein5@gmail.com> writes:

> Am trying to learn about implementing Finite State Automata in C++.
> One of my goals would be to use it to implement string-matching
> algorithms.  The aim is to improve my own computing ability -- I don't
> anticipate improving on the string-matching code that is already
> available.
>
> I don't really know where to begin for breaking into FSA (in C++).
> http://retis.sssup.it/~marco/files/lesson13-state_machine_implementations.pdf
> is a reference that readily comes up.  Do people think it is a good
> place to start?  If not, does anyone have any better suggestions?

Way too complex.  I have no idea what the author is doing there, but you
don't need 200 pages of complex subtypes and pointers to vtables and
goodness know what else.

An FSA is a simple thing.  Here is one that "accepts" any string of the
form abbb...bbba.

0: ('a', 1)
1: ('b', 1), ('a', 2)
2: accept

There are lots of ways to represent such thing in C or C++.  I am sure
you can come up a few in no time at all.

If you can't, ask.  It may well bring comp.programming back to life.

-- 
Ben.

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

Thread

Good resource for learning about implementing finite state automata in c++? Paul <pepstein5@gmail.com> - 2016-01-16 08:12 -0800
  Re: Good resource for learning about implementing finite state automata in c++? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-17 00:07 +0000

csiph-web