13 ms·

What is the enlightenment I'm supposed to attain after studying finite automata?

172 points by johndcook 14y ago

martinced 14y ago
It'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 gigantic mess. I ended up rewriting that part using an event-driven FSM and things became smooth. 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.
- stuffihavemade 14y ago
  You still create FSM's in functional languages though. Consider: data Light = On | Off toggle :: Light -> Light toggle On = Off toggle Off = On So, the data structures represent the possible states, and the associated functions the transitions.
- chas 14y ago
  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.
javajosh 14y ago
It is to recognize the congnizing that you are doing about finite automata is itself composed of finite automata.
- jmduke 14y ago
  Not to be rude, but what do you mean by this?
  - andrewflnr 14y ago
    (Your brain is a finite automaton) + (sliced "cognize" out of "recognize" to get a new word for thinking).
    - jacquesm 14y ago
      > Your brain is a finite automaton That assertion badly needs some proof, and I'm not currently aware that such a proof even exists (but I am aware that there is substantial evidence that it isn't all that simple). A 'finite automaton' implies that you can capture the complete state vector and for many reasons this is unfeasible. So if there is proof to the contrary then please supply it. (I understand you're merely transcribing the original comment, which to me feels clever but wrong).
  - javajosh 14y ago
    Recursion is the key to enlightenment. There are may ways to achieve this recursion, and contemplation of finite automata is one of them. The point of recursion happens when you realize that the thought process which is considering finite automata is itself composed of finite automata. The subjective experience of recursion leads to enlightenment.
    - dietrichepp 14y ago
      Chemical processes are not measurably discrete, so it is only a conjecture that the universe could be modeled as a finite automaton. Varying reference frames make it impossible to agree on an order for the input our brains receive, even if we can think of it as discrete. Agreeing on the state of a brain is also impossible, due to relativity. Quantum entanglement makes it impossible to accurately model a portion of the physical universe, such as a brain. If you want complete accuracy you must model the whole universe or none of it. I am aware of no accepted model of the universe that is deterministic. Finite automata are deterministic, the brain and the universe are not. Look up "hidden variables". Only a more sophisticated model than finite automata could possibly be useful for describing physical phenomena in general. All models are wrong, but finite automata are not even useful for describing brains.
chimeracoder 14y ago
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. 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 thinks in automata. 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.' 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. [1]http://en.wikipedia.org/wiki/Alfred_Aho http://en.wikipedia.org/wiki/Alfred_Aho
- jacquesm 14y ago
  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, quite possibly some genius would be able to solve it in many different ways, but this to me only underscores the value of statemachines as a tool).
  - plinkplonk 14y ago
    "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 https://www.coursera.org/course/automata
pekk 14y ago
If nothing else, it gives you an understanding of what regular expressions are doing, and a basis for understanding about the Chomsky hierarchy.
Adrock 14y ago
The answers given are great, especially the first. It's also nice to be able to express solutions as clearly and succinctly as you can with libraries like this: https://github.com/cdorrat/reduce-fsm https://github.com/cdorrat/reduce-fsm Not enlightenment, just bliss...
ctdonath 14y ago
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. A = {0|1,...} A[x] = !(A[y]•A[z]) That's all there is to computing, near as I've been able to simplify it. Cellular automata may do a better job.
- derleth 14y ago
  > Quantum mechanics is simple, but baffling to beginners Quantum mechanics is weird to us because we're human-sized and quantum effects are mostly gone at our scale. Therefore, the only language we have for actually doing quantum mechanics is mathematics, so it makes sense to get a firm grasp of the math first. Fortunately, the fundamentals of the math aren't that difficult. I like to think of quantum mechanics as being 'mind-bendingly simple' for that reason. Scott Aaronson has a fascinating lecture on quantum mechanics seen as a branch of probability theory: http://www.scottaaronson.com/democritus/lec9.html http://www.scottaaronson.com/democritus/lec9.html > Quantum mechanics is what you would inevitably come up with if you started from probability theory, and then said, let's try to generalize it so that the numbers we used to call "probabilities" can be negative numbers.
  - cynicalkane 14y ago
    And imaginary numbers, and four-vectors, and spinors...
  - disgruntledphd2 14y ago
    That's a wonderful link. I know very little about quantum mechanics (or physics in general) but I do know some linear algebra, and for me that was a wonderful revelation. Thank you for sharing.
btilly 14y ago
Apparently 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-exclusion-of-numbers/11317787 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-reopen-this-programming-question http://meta.stackoverflow.com/questions/138678/can-we-please... for the discussion on meta about the question, and http://news.ycombinator.com/item?id=4203350 http://news.ycombinator.com/item?id=4203350 for the HN discussion at the time. 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.
- mitchi 14y ago
  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.
  - frozenport 14y ago
    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 :-)
- krichman 14y ago
  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".
mcmatterson 14y ago
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. 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). I don't know that it's the enlightenment you're looking for, but it's the one that eventually found me.
- eternalban 14y ago
  > 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" that quite neatly -- at least in my mind -- map to a FA "fixed in space" [the cache line], with a "magical tape" [virtual memory and cache coherence].
  - jacquesm 14y ago
    The key insight is that they're essentially the same thing.
subhro 14y ago
Here is another set of lectures from IIT Madras India which helped me understand what Automata is all about. http://www.nptel.iitm.ac.in/courses/106106049/ http://www.nptel.iitm.ac.in/courses/106106049/
chrismaeda 14y ago
You're supposed to realize that enlightenment is not computable by an FA.
deleted 14y ago
[deleted]
- SecretofMana 14y ago
  You did a great job summarizing those topics concisely, but I have some quibbles about the P and NP stuff: 1. NP isn't the set of problems that can't be solved in a polynomial amount of time, but rather the set of problems that can be solved non-deterministically in polynomial time. This distinction is important, since this means by definition that P is a subset of NP, and furthermore means that uncomputable problems such as the Halting Problem do not belong in NP. 2. Your definitions for NP-completeness seem mixed up -- the polytime reduction property you're mentioning is the definition of an NP-hard problem, and you've said it backwards. If a problem is NP-hard, every problem in NP can be reduced to it in polynomial time (i.e. it is just as "hard" as every problem in NP). NP-completeness requires in addition to this the property that the problem itself is in NP. For example, although the Halting Problem is NP-hard, it is not NP-complete, since it is not in NP. NP-hardness of a problem can be shown by polytime reducing any NP-complete problem to it, since any problem in NP can be polytime reduced to the NP-complete problem.
  - charlesju 14y ago
    Sure, you're probably right. :)
wonderzombie 14y ago
Any good links about automata? I'm afraid I don't know much about this just yet, so I can't really appreciate it.
dschiptsov 14y ago
That you're one of them.)
DeepDuh 14y ago
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. 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.
pokesomesmot 14y ago
I don't understand why FA are so difficult for CS students to grasp. 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. So my question is, what enlightenment would I attain if I understood all the theory (instead of just the reality)? When I write programs, I write state machines.
robomartin 14y ago
"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. 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. 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. 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: // 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; 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: 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 It's really cool. Geeking-out just thinking about it. 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. 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. Again, today I could not imagine designing hardware or writing software without FSM's.
mcgwiz 14y ago
Applications: 1. deep understanding of regular expressions. 2. how to model and reason about complex workflows and business processes.

172 points by johndcook 14y ago

It'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 gigantic mess. I ended up rewriting that part using an event-driven FSM and things became smooth. 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.

stuffihavemade 14y ago
You still create FSM's in functional languages though. Consider: data Light = On | Off toggle :: Light -> Light toggle On = Off toggle Off = On So, the data structures represent the possible states, and the associated functions the transitions.
chas 14y ago
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.

javajosh 14y ago

It is to recognize the congnizing that you are doing about finite automata is itself composed of finite automata.

jmduke 14y ago
Not to be rude, but what do you mean by this?
- andrewflnr 14y ago
  (Your brain is a finite automaton) + (sliced "cognize" out of "recognize" to get a new word for thinking).
  - jacquesm 14y ago
    > Your brain is a finite automaton That assertion badly needs some proof, and I'm not currently aware that such a proof even exists (but I am aware that there is substantial evidence that it isn't all that simple). A 'finite automaton' implies that you can capture the complete state vector and for many reasons this is unfeasible. So if there is proof to the contrary then please supply it. (I understand you're merely transcribing the original comment, which to me feels clever but wrong).
- javajosh 14y ago
  Recursion is the key to enlightenment. There are may ways to achieve this recursion, and contemplation of finite automata is one of them. The point of recursion happens when you realize that the thought process which is considering finite automata is itself composed of finite automata. The subjective experience of recursion leads to enlightenment.
  - dietrichepp 14y ago
    Chemical processes are not measurably discrete, so it is only a conjecture that the universe could be modeled as a finite automaton. Varying reference frames make it impossible to agree on an order for the input our brains receive, even if we can think of it as discrete. Agreeing on the state of a brain is also impossible, due to relativity. Quantum entanglement makes it impossible to accurately model a portion of the physical universe, such as a brain. If you want complete accuracy you must model the whole universe or none of it. I am aware of no accepted model of the universe that is deterministic. Finite automata are deterministic, the brain and the universe are not. Look up "hidden variables". Only a more sophisticated model than finite automata could possibly be useful for describing physical phenomena in general. All models are wrong, but finite automata are not even useful for describing brains.

chimeracoder 14y ago

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. 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 thinks in automata. 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.' 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. [1]http://en.wikipedia.org/wiki/Alfred_Aho http://en.wikipedia.org/wiki/Alfred_Aho

jacquesm 14y ago
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, quite possibly some genius would be able to solve it in many different ways, but this to me only underscores the value of statemachines as a tool).
- plinkplonk 14y ago
  "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 https://www.coursera.org/course/automata

pekk 14y ago

If nothing else, it gives you an understanding of what regular expressions are doing, and a basis for understanding about the Chomsky hierarchy.

Adrock 14y ago

The answers given are great, especially the first. It's also nice to be able to express solutions as clearly and succinctly as you can with libraries like this: https://github.com/cdorrat/reduce-fsm https://github.com/cdorrat/reduce-fsm Not enlightenment, just bliss...

ctdonath 14y ago

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. A = {0|1,...} A[x] = !(A[y]•A[z]) That's all there is to computing, near as I've been able to simplify it. Cellular automata may do a better job.

derleth 14y ago
> Quantum mechanics is simple, but baffling to beginners Quantum mechanics is weird to us because we're human-sized and quantum effects are mostly gone at our scale. Therefore, the only language we have for actually doing quantum mechanics is mathematics, so it makes sense to get a firm grasp of the math first. Fortunately, the fundamentals of the math aren't that difficult. I like to think of quantum mechanics as being 'mind-bendingly simple' for that reason. Scott Aaronson has a fascinating lecture on quantum mechanics seen as a branch of probability theory: http://www.scottaaronson.com/democritus/lec9.html http://www.scottaaronson.com/democritus/lec9.html > Quantum mechanics is what you would inevitably come up with if you started from probability theory, and then said, let's try to generalize it so that the numbers we used to call "probabilities" can be negative numbers.
- cynicalkane 14y ago
  And imaginary numbers, and four-vectors, and spinors...
- disgruntledphd2 14y ago
  That's a wonderful link. I know very little about quantum mechanics (or physics in general) but I do know some linear algebra, and for me that was a wonderful revelation. Thank you for sharing.

btilly 14y ago

Apparently 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-exclusion-of-numbers/11317787 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-reopen-this-programming-question http://meta.stackoverflow.com/questions/138678/can-we-please... for the discussion on meta about the question, and http://news.ycombinator.com/item?id=4203350 http://news.ycombinator.com/item?id=4203350 for the HN discussion at the time. 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.

mitchi 14y ago
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.
- frozenport 14y ago
  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 :-)
krichman 14y ago
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".

mcmatterson 14y ago

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. 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). I don't know that it's the enlightenment you're looking for, but it's the one that eventually found me.

eternalban 14y ago
> 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" that quite neatly -- at least in my mind -- map to a FA "fixed in space" [the cache line], with a "magical tape" [virtual memory and cache coherence].
- jacquesm 14y ago
  The key insight is that they're essentially the same thing.

subhro 14y ago

Here is another set of lectures from IIT Madras India which helped me understand what Automata is all about. http://www.nptel.iitm.ac.in/courses/106106049/ http://www.nptel.iitm.ac.in/courses/106106049/

chrismaeda 14y ago

You're supposed to realize that enlightenment is not computable by an FA.

deleted 14y ago

[deleted]

SecretofMana 14y ago
You did a great job summarizing those topics concisely, but I have some quibbles about the P and NP stuff: 1. NP isn't the set of problems that can't be solved in a polynomial amount of time, but rather the set of problems that can be solved non-deterministically in polynomial time. This distinction is important, since this means by definition that P is a subset of NP, and furthermore means that uncomputable problems such as the Halting Problem do not belong in NP. 2. Your definitions for NP-completeness seem mixed up -- the polytime reduction property you're mentioning is the definition of an NP-hard problem, and you've said it backwards. If a problem is NP-hard, every problem in NP can be reduced to it in polynomial time (i.e. it is just as "hard" as every problem in NP). NP-completeness requires in addition to this the property that the problem itself is in NP. For example, although the Halting Problem is NP-hard, it is not NP-complete, since it is not in NP. NP-hardness of a problem can be shown by polytime reducing any NP-complete problem to it, since any problem in NP can be polytime reduced to the NP-complete problem.
- charlesju 14y ago
  Sure, you're probably right. :)

wonderzombie 14y ago

Any good links about automata? I'm afraid I don't know much about this just yet, so I can't really appreciate it.

dschiptsov 14y ago

That you're one of them.)

DeepDuh 14y ago

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. 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.

pokesomesmot 14y ago

I don't understand why FA are so difficult for CS students to grasp. 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. So my question is, what enlightenment would I attain if I understood all the theory (instead of just the reality)? When I write programs, I write state machines.

robomartin 14y ago

"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. 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. 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. 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: // 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; 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: 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 It's really cool. Geeking-out just thinking about it. 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. 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. Again, today I could not imagine designing hardware or writing software without FSM's.

mcgwiz 14y ago

Applications: 1. deep understanding of regular expressions. 2. how to model and reason about complex workflows and business processes.