pages tagged automatayakkinghttp://yakking.branchable.com/tags/automata/yakkingikiwiki2016-04-13T11:00:16ZFinite Automatahttp://yakking.branchable.com/posts/finite-automata/Daniel Silverstone2016-04-13T11:00:16Z2016-04-13T11:00:08Z
<p>A topic which often comes up as one gets deeper into computer science is that
of <a href="https://en.wikipedia.org/wiki/Finite-state_machine">finite-state automata</a>. Finite automata are sometimes
known as <a href="http://yakking.branchable.com/posts/state-machines-in-c/">state machines</a> and Richard has talked about concrete
implementation considerations already. However an FSM can be used to describe
significantly more than you might already think. Learning how to manipulate
FSMs can lead to a deeper understanding of several parts of computer science
such as <a href="https://en.wikipedia.org/wiki/Lexical_analysis">lexical analysis</a>, <a href="https://en.wikipedia.org/wiki/Parsing">parsing</a>, <a href="http://yakking.branchable.com/tags/regexp/">regular expressions</a>.</p>
<p>In brief, as a data structure, an FSM is a collection of states, a collection
of input atoms (also known as the alphabet of the FSM), and a collection of
triplets consisting of input state, input, and output state. The vast majority
of FSMs you encounter in your day-to-day programming life shall be of the kind
in Richard's article, namely <a href="https://en.wikipedia.org/wiki/Deterministic_finite_automaton">deterministic finite state automata</a>. However
when one delves deeper into the wonderful world of FSMs, one discovers that
more flexible and more easily composed cousin, the <a href="https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton">non-deterministic finite
state automaton</a> or NFA.</p>
<p>The non-deterministic automaton has one specific advantage over its
deterministic cousin -- the ability to express indecision through the
possibility that a given input atom might transition the NFA to zero, one or
more possible states, rather than always to exactly one state.</p>
<p>One further extension of this is needed to give us the most flexible variant of
FSMs. This is often called the <a href="https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton_with_%CE%B5-moves">ε-move</a> and it allows an NFA-ε to transition
from one state to another without consuming an input atom at all.</p>
<p>While it's very easy to write code which represents a DFA, and pretty simple
to reason about it; reasonably easy to write code which represents an NFA, and
not too hard to reason about it; it's pretty hard to write code which usefully
represents an NFA-ε and it can be very hard to reason about them.</p>
<p>Fortunately for us, NFA-εs are both helpful, and relatively easy to
<a href="https://en.wikipedia.org/wiki/Powerset_construction">transform</a> into DFAs later (though that act often expands the storage space
required for the FSM quite substantially).</p>
<p>One directly applicable use of building NFA-εs, composing them together, and
then converting them to DFAs, is in the construction of regular expression
engines. Your homework is to have a look at one of the many descriptions of
regular expressions, liken it to an understanding of FSMs from the linked
articles on this page, and then have a go at writing a very simple regexp
engine for yourself in whatever language you favour. Though I'd recommend
using a scripting language if you can, for rapid development and debugging.
If you get very stuck you could look to <a href="http://www.gamedev.net/page/resources/_/technical/general-programming/finite-state-machines-and-regular-expressions-r3176">this article</a> for further discussion
of FSMs and how to do this.</p>