DFA (Deterministic Finite Automata) Explained

Timothy Washington

— 1 min read
Share

I usually need some kind of reason to fly off on the handle like this. But for some reason, I'm thinking of and trying to refine my mental model of a DFA. See chapter 2.2 "Grammars" from  Etienne Gagnon's thesis paper where he describes it in detail. Feel free to comment, correct or embellish. So here goes.

A DFA is a theoretical machine that is defined by a mathematical model that describes a context-free grammar. A context free-grammar is a set of rules that define the structure and semantics (meaning) of a language.
We say "context-free" to describe the grammar as something that does not remember what was previously expressed. So your brain reading this post remembers that I began describing what a DFA was; then describing what a context free grammar was. A DFA interpreting expressions in a context-free grammar doesn't remember, or logically incorporate the description of a DFA into the description of a context free grammar. It simply interprets the validity and meaning of those 2 expressions.

Just in case you were wondering ;-)

Posted by  on 2007.11.07| Original post

#archive #frye #thebox

Read more