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

Groups > comp.programming > #6222 > unrolled thread

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

Back to article view | Back to comp.programming

Contents

  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

#6222 — Good resource for learning about implementing finite state automata in c++?

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?

Thanks,

Paul

[toc] | [next] | [standalone]

#6223

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.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web