Here is another set of lectures from IIT Madras India which helped me understand what Automata is all about.
What is the enlightenment I'm supposed to attain after studying finite automata?
21–30 of 66 posts
Re: What is the enlightenment I'm supposed to attain after studying finite automata?
#22Earlier quoted context omitted.
Consider me extremely jealous that you are studying under Prof. Aho, he's one of the greats. Statemachines are an incredibly useful tool. I've spent the better part of last year untangling a huge pile of code and the solution in the end was to split it all up into statemachines that communicate with each other using simple synchronous messages. That and that alone made the problem tractable. (Tractable to me, that is…
"Consider me extremely jealous that you are studying under Prof. Aho, he's one of the greats." If you don't mind being taught by Prof Ullman instead, Coursera has a course on Automata coming up https://www.coursera.org/course/automata
The other half of the dragon book... figures :)
Re: What is the enlightenment I'm supposed to attain after studying finite automata?
#23Earlier quoted context omitted.
Consider me extremely jealous that you are studying under Prof. Aho, he's one of the greats. Statemachines are an incredibly useful tool. I've spent the better part of last year untangling a huge pile of code and the solution in the end was to split it all up into statemachines that communicate with each other using simple synchronous messages. That and that alone made the problem tractable. (Tractable to me, that is…
Would love to get your recommendations for good reading on state machines, please. Getting curation from a someone who understands them well and uses them in practice often would be fantastic.
I first learned about them from a digital logic perspective, so they were already very practical tools for me when I ran into them in my theory classes. One of the best free resources I can find in short order is the wiki article on them. http://en.wikipedia.org/wiki/Finite-state_machine The wiki page on deterministic finite automata would be useful to see the CS theory/language side of the idea. http://en.wikipedia.org/wiki/Deterministic_finite_automaton
Re: What is the enlightenment I'm supposed to attain after studying finite automata?
#24It's interesting that both the question and the answer do focus on pattern matching. I maybe mistaken on this but that is really just one use of FSMs. 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 gig…
I don't think you need to abandon the S. I think FSMs embody the core of functional thinking. Structuring your computation as a FSM splits your code into your current state and a combinatorial logic block that takes a current state and outputs a new state along with some optional side-effects. Splitting your computations into pure functions that hold state on their end-points sounds very much like the philosophy behind FP.
Re: What is the enlightenment I'm supposed to attain after studying finite automata?
#25Apparently if you understand finite automata, you'll be more enlightened than Stack Overflow moderators. My bitter example for this is http://stackoverflow.com/questions/11314077/algorithm-for-ex... which question was deleted by moderators, then undeleted by HN members. See http://meta.stackoverflow.com/questions/138678/can-we-please... for the discussion on meta about the question, and http://news.ycombinator.com/it…
I find there's no point in participating in SO beyond a certain level of ability. If you ask a truly difficult question, the odds of getting an answer from someone who knows what they are talking about is not very good. Meanwhile, any sort of discussion question gets closed.
The remainder is basic to intermediate questions that get answered with "this is a duplicate of X".
Re: What is the enlightenment I'm supposed to attain after studying finite automata?
#26Earlier quoted context omitted.
Consider me extremely jealous that you are studying under Prof. Aho, he's one of the greats. Statemachines are an incredibly useful tool. I've spent the better part of last year untangling a huge pile of code and the solution in the end was to split it all up into statemachines that communicate with each other using simple synchronous messages. That and that alone made the problem tractable. (Tractable to me, that is…
Would love to get your recommendations for good reading on state machines, please. Getting curation from a someone who understands them well and uses them in practice often would be fantastic.
Hm, I never thought there would be anybody interested in this stuff so it's all over the place.
Basically what I've done is to model state machines using a bunch of C macros, added a simple event system to drive the state transitions (receipt of message translates into an event) which allows you to run any number of statemachines in parallel inside a single C thread.
The events are prioritized to make sure that urgent stuff gets processed first (such as statemachines terminating).
Imagine turning a very large bowl of spaghetti into a neatly ticking Swiss watch :)
The particular element that made this a powerful tool was the fact that statemachines (unlike function calls) are restrictive, the state-to-state transitions are all known up front and any state changes that are not explicitly allowed are forbidden. This simplifies design and debugging. An extra benefit of doing it this way is that to run the resulting code on a cluster requires only one (relatively, see 'fallacies of distributed computing') simple addition, a way to pass messages between statemachines on different nodes.
The end result of all this is that what was an absolutely gargantuan knot of hard to read code became almost trivial by comparison, each statemachine is so simple that the business logic portion is usually less than a page of code or so (with a few exceptions), and all of the boilerplate is abstracted out and taken care of by the macros.
Statemachines are small enough that they can be tested with ease and can then be glued together using instantiation from within other statemachines.
The main loop of the program reads input and as soon as it has a complete message will instantiate a statemachine to process it and will then send that statemachine the message to set the ball rolling.
I'll see if I can find the time to describe the method in a bit more detail, statemachines communicating using messages is a powerful metaphor for many programming problems and I think it comes into its own when you're making really complicated systems that have to be very predictable and reliable.
Note that even though there are some parallels with threads threads are simply multiple paths of execution running in parallel through the same body of code, statemachines are different in that instead of functions calling other functions statemachines operate on a single chunk of data (called the state) and will note the changes to the state by transiting to a new state. Every program you write is in essence a statemachine but you normally don't make the states explicit, instead you embody the (single) state that you've got in the combination of program counter, stack and data memory. That makes the state rather hard to untangle at any given moment.
Using statemachines explicitly breaks up this giant state vector into smaller ones that operate on much simpler pieces of data using a series of permitted operations, the outcome of which is rigidly defined.
I hope this all makes sense (it's 6:15 am and I haven't slept yet...)
Re: What is the enlightenment I'm supposed to attain after studying finite automata?
#27Honestly, 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,…
> 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 would seem an apt analogy for the (basic) Von Neumann architecture, but "modern" CPUs have a hierarchy of "cache lines…
The key insight is that they're essentially the same thing.
Re: What is the enlightenment I'm supposed to attain after studying finite automata?
#28You're supposed to realize that enlightenment is not computable by an FA.
Re: What is the enlightenment I'm supposed to attain after studying finite automata?
#29Apparently if you understand finite automata, you'll be more enlightened than Stack Overflow moderators. My bitter example for this is http://stackoverflow.com/questions/11314077/algorithm-for-ex... which question was deleted by moderators, then undeleted by HN members. See http://meta.stackoverflow.com/questions/138678/can-we-please... for the discussion on meta about the question, and http://news.ycombinator.com/it…
Yep, this is the stackoverflow I know. They have practically killed all the meaningful C++ activity on the website by closing duplicate questions. Maybe some easy questions have already been answered but they don't let junior members contribute by answering them. By the way Wikipedia is worse. In English anyway, in French it's cool.
Wikipedia carries with it a political edge. Companies pay good money to protect their reputation and apparently every central country was the true cradle of civilization. The most I have seen on SO is bored NVIDIA engineers answering questions related to the CUDA tag :-)
Re: What is the enlightenment I'm supposed to attain after studying finite automata?
#30[deleted]