I was dreading taking Computer Science Theory for my undergraduate degree. Turing machines bored me when I studied them in my introductory class, and I saw the class as a necessary evil - a core requirement as well as a prerequisite for my compilers class.<p>Boy, was I wrong. Despite what I'd anticipated, that class ended up being the single most useful CS class that I took. I had the fortune of taking the class with Alfred Aho[1] - I can't imagine a person more qualified to teach a class on computation via automata; he literally <i>thinks</i> in automata.<p>One day, I mentioned how I'd solved a particular programming problem (not for class) by reasoning about it as if it were a pushdown automaton, and how I was surprised that these techniques were still relevant, even for problems far more high-level than, say, writing egrep. He told me, 'Sometimes when I have a tough problem, I like to think of it as a language recognition problem, and it becomes easier to solve.'<p>My brain may not be quite as oriented towards state machines as Prof. Aho's is, but that trick has saved me countless times. Like functional programming, it takes a bit of practice to wrap your head around it if you're not used to it, but it can present really elegant solutions to problems that seem daunting at first glance.<p>[1]<a href="http://en.wikipedia.org/wiki/Alfred_Aho" rel="nofollow">http://en.wikipedia.org/wiki/Alfred_Aho</a>
Honestly, my answer to this came about many years after living through a very theoretical CS undergrad, by way of a chapter in Charles Petzold's book, 'Code' (of all things. I originally bought the book for my dad to help him understand 'what it was I did all day'). Basically, the insight centered around the physicality of how FA are taught; FA are usually taught by thinking of the FA itself as being fixed in space, and the tape as moving through it. I always found that this lead to me thinking of the FA as a mechanical entity, driven by some sort of magical tape; a useful thought exercise to be sure, but not something that had many direct impacts on modern computing (outside of the obvious regular language avenues). If you instead envision a FA as being a flying head that moves back and forward across a tape that is fixed in space, the ideas behind modern CPUs become much more clear: the tape is memory, the FA is a CPU being stepped through successive states, and the 'location' of the FA is the PC register. It's a seemingly small difference of conception, but one that finally brought together two worlds for me that had evolved largely distinctly before then.<p>It's tough to give justice to this insight, except to say that it really helped crystalize the jump between the theoretical side of CS (which had always been clear to me, if never terribly 'real'), and the applied side of CS (which had always seemed to have evolved in some sort of semi-influenced paralel universe to theory).<p>I don't know that it's the enlightenment you're looking for, but it's the one that eventually found me.
Apparently if you understand finite automata, you'll be more enlightened than Stack Overflow moderators.<p>My bitter example for this is <a href="http://stackoverflow.com/questions/11314077/algorithm-for-exclusion-of-numbers/11317787" rel="nofollow">http://stackoverflow.com/questions/11314077/algorithm-for-ex...</a> which question was deleted by moderators, then undeleted by HN members. See <a href="http://meta.stackoverflow.com/questions/138678/can-we-please-reopen-this-programming-question" rel="nofollow">http://meta.stackoverflow.com/questions/138678/can-we-please...</a> for the discussion on meta about the question, and <a href="http://news.ycombinator.com/item?id=4203350" rel="nofollow">http://news.ycombinator.com/item?id=4203350</a> for the HN discussion at the time.<p>Incidentally the answer to that question provides a concrete example of something you can easily do if you understand finite automata, that you couldn't do without it, and that knowing how to use pre-built interfaces with finite automata behind them (like regular expressions) would not help you solve.
The concepts themselves have helped me a lot when programming parsers / interpreters / compilers. Recently I've developed a language extension for Fortran 90 along with a parser/analyzer in python that extracts structural information of the the program as well as the additional directives. Solved it in <1000 lines of python by combining an FA like structure (state switch using a dictionary function lookup with a state variable inside a loop) with regular expressions for the individual lines / state transitions. Sure, you could come up with this on your own quite easily, but FA give you some powerful concepts - even just knowing the keywords to google for can save you days of work.<p>The gist: When it comes to computer science and mathematical concepts, don't ask why to study it, just study it - possible applications will probably come at some point later in your career.
When you understand a subject well enough, the true basics become fascinating. Without the full round trip from introduction to complexity to revealed simplicity, the basics are nigh unto incomprehensible - yet giving new students an intro thereto at least shows them where they are going. Quantum mechanics is simple, but baffling to beginners; give them a taste and the "aha" moment will come in time.<p>A = {0|1,...}<p>A[x] = !(A[y]•A[z])<p>That's all there is to computing, near as I've been able to simplify it. Cellular automata may do a better job.
I don't understand why FA are so difficult for CS students to grasp.<p>I have the reverse problem. The concept of FA makes perfect sense. It's how I naturally think of a computer. It's the theory stuff that is not based on state machnes which I can't get my head around.<p>So my question is, what enlightenment would I attain if I understood all the theory (instead of just the reality)?<p>When I write programs, I write state machines.
The answers given are great, especially the first.<p>It's also nice to be able to express solutions as clearly and succinctly as you can with libraries like this:<p><a href="https://github.com/cdorrat/reduce-fsm" rel="nofollow">https://github.com/cdorrat/reduce-fsm</a><p>Not enlightenment, just bliss...
Here is another set of lectures from IIT Madras India which helped me understand what Automata is all about.<p><a href="http://www.nptel.iitm.ac.in/courses/106106049/" rel="nofollow">http://www.nptel.iitm.ac.in/courses/106106049/</a>
"Aha! moment". Well, I have to say that, for me, this came with the practice, not the study, of FSM's and, in particular Turing Machines. I could not imagine a world without them. Look around you.<p>While I studied FA formally it never really clicked until years later. Sometimes you don't really learn until you are holding a cat by the tail.<p>I should say that I've always called them "FSM" when, in most cases, in reality I was using a TM. A TM, of course, is also an FSM, so I'm at peace with my loose use of the term.<p>I really started to use FSM's with great frequency while working on developing hardware with FPGA's. Everything from reset modules to FIFO and SD/DD RAM controllers and more benefit from FSM's. They greatly reduce complexity and allow you to express very complex logic in code that can actually be followed and understood. For some reason FSM's feel more "at home" in hardware rather than software for me (although I use them extensively in software as well). There's something about looking at the definition of an FSM's states and realizing that it's a bunch of single bits (flip-flops) that makes it real:<p><pre><code> // Fictitious example
parameter STATE_RESET = 5'b00001;
parameter STATE_STOP = 5'b00010;
parameter STATE_FORWARD = 5'b00100;
parameter STATE_TURN_RIGHT = 5'b01000;
parameter STATE_TURN_LEFT = 5'b10000;
</code></pre>
Later, when you code the FSM --and if you've been doing this for a while-- you can look at the code and almost literally see the flip-flops and latches forming the structure:<p><pre><code> always @ (posedge SOME_CLK) begin
case(state)
STATE_RESET: begin
// Do something in this state
end
STATE_STOP: begin
// Do something in this state
end
STATE_FORWARD: begin
// Do something in this state
end
STATE_TURN_RIGHT: begin
// Do something in this state
end
STATE_TURN_LEFT: begin
// Do something in this state
end
endcase
end
</code></pre>
It's really cool. Geeking-out just thinking about it.<p>In the software front, everything from communications packet processors to email address validation and menu processors benefit from using FSM's. I like the application of FSM's to web app controllers where you can encode a lot of knowledge and sophistication into your control module and not end-up with a huge rats-nest of procedural code that is nearly impossible to understand and maintain.<p>I have to admit being guilty of "thinking like an FSM" at times to the extent that I see the opportunity to use them in almost every project, hardware or software.<p>Again, today I could not imagine designing hardware or writing software without FSM's.
It's interesting that both the question <i>and</i> the answer do focus on pattern matching. I maybe mistaken on this but that is really just one use of FSMs.<p>I've implement event-driven FSMs and to me the biggest "ah ah" moment was that it was trivial to make a list of valid (or non valid) state transitions. I used it in one particular case which was really complex (IMHO) to model and were my code was quickly becoming a gigantic mess. I ended up rewriting that part using an event-driven FSM and things became smooth.<p>Nowadays I don't like the 'S' in "FSM" that much anymore: I've moved to FP and can't really say I'm missing mutability.