9 ms·

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

336 points by netvarun 13y ago

PaulHoule 13y ago
I'd say that finite automata give practical answers to many parsing problems which would be difficult otherwise.
netvarun 13y ago
I had come across this answer some time back, but got to revisit it again while reading another one of the author's (Vijay D. - http://www.eecs.berkeley.edu/~vijayd/#about http://www.eecs.berkeley.edu/~vijayd/#about ) answers trending on HN (https://news.ycombinator.com/item?id=6787836 https://news.ycombinator.com/item?id=6787836) Additional discussion: https://news.ycombinator.com/item?id=6788969 https://news.ycombinator.com/item?id=6788969
blibble 13y ago
on examinations of code it's normally pretty easy to see who has a formal understanding of state machines, and who doesn't.
- sateesh 13y ago
  Would you please elaborate. My experience has been that formal understanding of theory (say of state machines) equips one to handle complex problems and in no way indicates how well the code is written. For example, a GUI application code (say) making use of a framework wouldn't give any indication of whether the author had any formal understanding of state machines or not. In my opinion to write a good readable code one need not have a formal understanding of CS theory, but the understanding of CS theory is paramount in writing code for complex problems (say writing a compiler).
  - blibble 13y ago
    7 booleans to try and maintain state instead of a single enum value happens quite a lot in my experience
  - PeterisP 13y ago
    GUI application code actually is one that often can be very clearly thought as a DFA. In particular, the UI often is non-static and can be in certain states, with the effect of user actions (and possibility of certain actions) depending on that state. If it is implemented or "grown" ad-hoc, it sometimes may turn into a jumble of interdependent code and flag/visibility variables, but very often the exact same behaviour can be modelled and implemented much simpler if you think of it as a DFA. For example, the UI of recently popular single-page webapps, where JS is used to change 'screens' without page load, or change functionality by hiding/adding large parts of the page, can often be naturally be thought of as DFA, planned (on paper or wireframes) as states='screens' and transitions between them, and then implemented as DFA. Thinking of UI as a DFA also forces you to consider the 'proper' effect of every user action in every state, which is just good UX practice. For example, in a classic url-based web app you may draw a graph/process of how an user proceeds through making a purchase on your site. Usually it will include only the typical process - but if you think of it as a DFA, you define behavior for actions such as 'requested url /ordervalidation/step2-address' at every state, since the result likely should be different depending on if the user went there from step1 by clicking 'ok, i want to buy this', step3 by clicking the back button, or two weeks later by clicking on a link that he accidentally bookmarked.
- tjgq 13y ago
  Can you please elaborate?
raverbashing 13y ago
I have to say I am very happy with this discussion and the "data structures in the Linux Kernel" Such theoretical basis (and even their practical considerations) seems much more important than "What are the advantages of latest fad.js"
- morganwilde 13y ago
  I totally support this statement. Longterm thinking is based on first principles. [edit] Should be based on first principles.
  - eruditely 13y ago
    This requires empirical support.
- calt 13y ago
  This post inspired me to up-vote. It's amazing how popular hacker news tends to be among the people I talk to but how few votes it can take to be on the front page.
- mcphilip 13y ago
  Agreed, with the caveat that I can only handle a couple of posts this deep before feeling intimidated and longing for something more lightweight. I like the mix of articles because if all of them were this deep it would feel like I don't belong here without years of prerequisite study.
- manojlds 13y ago
  Note that both the top answers are from the same person.
ape4 13y ago
What's the best book on this? (I'd prefer something non-academic)
- sateesh 13y ago
  Chapter 10 of the book "Foundations of Computer Science" (http://i.stanford.edu/~ullman/focs.html http://i.stanford.edu/~ullman/focs.html) which is available online provides an excellent introduction to automata theory. After that you can start referring to " Introduction to Automata Theory, Languages, and Computation" by Ullman, Hopcraft and Motwani. This is also the reference book for the Automata course (and taught by Ullman) currently being available in Coursera.
- tomstuart 13y ago
  I wrote a non-academic book on this subject for the HN crowd: http://computationbook.com/ http://computationbook.com/
- justin66 13y ago
  I took a quick look at Tom Stuart's book and it looks great (thanks for sharing that, Tom! something new on my reading list). Somewhere in between that and Ullman's stuff in terms of formality is Sipser's Introduction to the Theory of Computation. I like its explanations of the DFA material more than the free Ullman book online, though I haven't read Ullman's dedicated Automata title. (A little too rich for my blood...)
diminish 13y ago
If you're interested in learning Automata from Prof. Jeff Ullman of Stanford you may join the current session on Coursera. What's best about this course is that Prof. Ullman is always present in discussion forums, and helps everyone learn and enjoy great discussions. Join here https://www.coursera.org/course/automata https://www.coursera.org/course/automata Edit: I'm currently learning there, and enjoy it a lot. Especially in video 6, you may listen to the stories of Junglee startup, Started in the mid-90’s by three of his students, Ashish Gupta, Anand Rajaraman, and Venky Harinarayan. Goal was to integrate information from Web pages. Bought by Amazon when Yahoo! hired them to build a comparison shopper for books. They made extensive use of regular expressions to scrap..."
- brudgers 13y ago
  The Coursera Automata course is awesome. Ullman's active participation in the current second offering is part of it. But what really makes the course for me is that Ullman's presentations are relaxed. He knows the material, he knows where various aspects of the material rank in terms of importance to the learner, he has a feel for where students will get hung up, and he has no need to prove anything. Ultimately, this gives the class the feel of a graduate seminar. It is designed so that student's can readily succeed in learning the material rather than structured around the idea of weeding out weaker students. It assumes that anyone who wants to learn the material can with enough effort, and that that learning is really all that matters.
  - sateesh 13y ago
    In addition to the lectures what has made the course interesting to me is the vibrant, active "Discussion Forum" associated with this course. Ullman himself frequently posts explanation on some of the topics here. It seems there are some takers of this course who are well versed with Automata theory. Some of them are quite active in the discussion forum providing good explanation to many of the trickier concepts introduced in the course (which has been immensely valuable to me).
    - brudgers 13y ago
knicholes 13y ago
Oh yeah-- Without studying finite automata, writing my compiler would have sucked. [edited] would have sucked even more
en4bz 13y ago
I originally went into my Theory of Computation class this year grunting and moaning about it was a waste of time and how I would rather be writing actually software. Now I actually kind of enjoy the class and can see its use. I find the discussion on Decidability to probably be one of the most important part. Although it's a little disappointing to find out that there are some problems that we will never be able to solve.
robdd 13y ago
ROBDD: Reduced Ordered Binary Decision Diagram A flow chart with a truth table, which is used to map all of the possible ways to arrive at one or zero by carrying out a set of steps, which may follow recursive paths, such that the similarities of different paths to identical outcomes can be better understood. Where ( reduced = all roads lead to one or zero ) and ( ordered = applying good organization to the steps of the decisions in the flow chart, even when steps in the decision tree can be carried out in a variety of ways )
itistoday2 13y ago
I didn't study finite automata at school, but I studied cellular automata on my own. If anyone would like to describe the difference (if there is one), it'd be appreciated. W.r.t cellular automata, I made this video, and if this isn't enlightenment, I don't know what is: https://vimeo.com/80147310 https://vimeo.com/80147310
- theseoafs 13y ago
  Cellular automata are one of the things you study in automata theory, which is the study of different models of computation. Although cellular automata are of some interest (Game of Life is Turing-complete, etc.), I wouldn't say they're nearly as important as the other models of computation you'd study in a normal undergraduate class (DFA's/NFA's, PDA's, Turing Machines).
  - itistoday2 13y ago
    Thanks! Much obliged for the explanation (and damn anyone who downvotes me for an expression of gratitude!).
t1m 13y ago
New appreciation for the goto statement.
Confusion 13y ago
The link does not answer the question. The answer is: there is no enlightenment you're supposed to attain immediately after studying finite automata. You've created the possibility for enlightenment further down the road. Studying finite automata equips you with a bunch of knowledge about their behavior, which equips you with a bunch of knowledge about the behavior of a variety of other subjects, because they can be projected onto automata (can be reduced to automata, can be morphed into automata, ...). The link lists a bunch of properties of, and relations between, various kinds of FA's and explains how these are useful to other areas of CS and even to regular programming. But you cannot be expected to have these thoughts as sudden epiphanies. At most you can at a later time realize a certain property exists, realize the same property exists for FA's and realize that makes sense, because of the relation between your subject and FA's. You can then further realize that you know immediately know a lot more about the subject as well. Some of these realizations may strike you with a physically tingling sensation of aesthetically pleasantness which some call 'enlightenment', but YMMV.
- andrewflnr 13y ago
  The question did not stipulate an "immediate" enlightenment. If that's what you wanted fine, but the question as asked was answered just fine.
lindig 13y ago
You might realise that parsing HTML or C with regular expressions is a bad idea.
- laureny 13y ago
  Really? http://stackoverflow.com/a/1732454/162410 http://stackoverflow.com/a/1732454/162410
- UNIXgod 13y ago
  It's tricky with HTML but can be done. The C language was one of it's initial use cases.
  - theseoafs 13y ago
    No, it can't. As in, you cannot parse HTML or C with regular expressions, and you can prove that that's the case. Regexes simply aren't powerful enough. This is one of the advantages of studying formal languages -- you get to learn about really useful models of computation (here, DFA's), but you also get to learn about their limits.
  - dllthomas 13y ago
    Scanning the C language is done using regular expressions, typically. Parsing the resulting token stream cannot be done with only regular expressions. At least not with the theoretical construct. Some "regular expressions" libraries, notably PCRE, let you do plenty that goes beyond the theory at the expense of some efficiency. Parsing some context-free grammars with these libraries is certainly possible, but you're not really restricting yourself to "just" regular expressions at that point. Regular expressions plus interwoven use of a stack is a pushdown-automata, which can totally parse C and HTML.
- dllthomas 13y ago
  Parsing C or HTML with regular expressions is a great idea. Parsing C or HTML with only regular expressions isn't.
mrottenkolber 13y ago
I'd say after learning about different classes of automata, you should understand what a compiler does in general. At least, that's what I took from it.
chubot 13y ago
A modern processor has a lot in it, but you can understand it as a finite automaton. Just this realisation made computer architecture and processor design far less intimidating to me. It also shows that, in practice, if you structure and manipulate your states carefully, you can get very far with finite automata. I don't understand this one. Surely a modern processor is like a Turing machine and not a finite state automata. For example, a DFA/NFA can't express simple algorithms like matching parentheses, while obviously a modern processor can.
- loup-vaillant 13y ago
  The processor plus the RAM is a Turing machine. If you decide in advance what input go to the input pins, regardless of the output, and you just record what goes out the output pins, the processor is pretty much a DFA. When you add the RAM, you provide a feedback loop: input depends on previous outputs (in plainspeak, when you write to the RAM, you can read it later). No feedback loop, no Turing machine.
- andrewaylett 13y ago
  It's basically because you don't have infinite storage -- I could, given enough time, feed your PC a string that it wouldn't be able to tell was unbalanced. Of course, to do that I would have to overflow your available storage which would take a while. For all practical purposes, your PC adequately models a Turing machine. In point of literal fact, it doesn't because it only has finite storage. In practical usage, it is sometimes helpful to consider various states your code may enter and how they interact. For understanding how the system actually works, the author appears to have found the state-switching model to be a useful one, and indeed I understand that it's common to model the internal state of various devices using finite automata.
  - chas 13y ago
    A PC can still read and write from arbitrary memory locations which means it can know a lot about it's past states, so the memory limit makes it a deterministic linear-bounded automata. http://en.wikipedia.org/wiki/Linear_bounded_automaton http://en.wikipedia.org/wiki/Linear_bounded_automaton
undoware 13y ago
...cannot be played on record player B.
Adrock 13y ago
The list in the 1st answer is amazing, but the 2nd highest answer has one of my favorite things: > Turing machines (we think) capture everything that's computable. However, we can ask: What parts of a Turing machine are "essential"? What happens when you limit a Turing machine in various ways? DFAs are a very severe and natural limitation (taking away memory). PDAs are a less severe limitation, etc. It's theoretically interesting to see what memory gives you and what happens when you go without it. It seems a very natural and basic question to me. I like to think of it the other way, though. A DFA with a stack is a PDA. A DFA with two stacks is a Turing machine. Looking at the 3 different classes as DFAs with 0, 1, or 2 stacks is just so beautiful...
- alok-g 13y ago
  Adding to the above: While in most algorithms books, we treat integer operations (addition, multiplication) as an O[1] operation, most do not even mention that this is only because these integers are constrained in size to a limited number of bits. Storing an integer in mathematics would require infinite amount of memory. Analyzing the Big-O complexity of the algorithms is too much more fun when you take the integer fixed-width assumption out. A single integer can serve as a "stack" from the perspectives of computer science. Without loss of generalization, assume that the set of symbols has digits 1..9. Now push operation is multiplication by ten and addition of the digit, while pop is taking the units digit and dividing by ten. In other words, if you are using a single integer in your program, and do not want to simply return incorrect answers or throw exceptions due to overflow errors, then your algorithm may already be beyond an NDFA. This would for example happen if you are trying to match parenthesis in a string like "(()())(((())))". You can easily do this by having an integer in your program, reading the string from left to right, incrementing the integer when you encounter a '(' and decrement for a ')'. The computer science books would however show the above problem to be unsolvable using a NDFA. (You have solved the problem for all practical purposes since the strings you'll encounter may never be that long, but a computer with finite memory is in principle incapable of solving this "correctly" for all possible inputs.)
- SandyPark 13y ago
  How is a Turing Machine a DFA with two stacks? I never learned it like that in my Theory of Computation course...
jmount 13y ago
Suffix Trees. That kind of hyper efficient recognition is even harder to think about without the finite automata theory behind regular expressions.
- crb002 13y ago
  I posted this above. Micron is releasing a new NFA card http://www.micron.com/about/innovations/automata-processing http://www.micron.com/about/innovations/automata-processing Any guess on which formerly expensive NFA algorithms will be put to use on it in short order?
crb002 13y ago
This. Micron's in memory automata is going to eat your lunch on many algorithms. Bye bye Van Neuman bottleneck. http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CC8QFjAA&url=http%3A%2F%2Fwww.micron.com%2F~%2Fmedia%2FDocuments%2FProducts%2FOther%2520Documents%2Fautomata_processing_technical_paper.pdf&ei=yj-SUqTUKdLtqQH_4YGYAg&usg=AFQjCNH9ikjKujCHM2h-10UN-9puwIx1qw&sig2=Fdv6xqQFXWM2Jlk1kQ4s1g&bvm=bv.56988011,d.aWM http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd...
- crb002 13y ago
  Press release: http://www.micron.com/about/innovations/automata-processing http://www.micron.com/about/innovations/automata-processing
GhotiFish 13y ago
>Turing machines (we think) capture everything that's computable. ?? eh?! we think? Isn't the definition of computable, "something that can be reached by a Turing machine?"
- Grothendieck 13y ago
  There's good evidence that Turing machines do capture the right notion of computability. You can enhance a Turing machine in many ways without changing what it can compute. Further, Turing machines, the lambda calculus, recursive functions, cellular automata, and register machines all give the same notion. Even a quantum computer can be simulated by a Turing machine. https://en.wikipedia.org/wiki/Church-turing_thesis https://en.wikipedia.org/wiki/Church-turing_thesis
- argv_empty 13y ago
  That's the definition when "computable" is used in a formal setting. What we believe is that it is also equivalent to our informal, intuitive understanding of the term.
austinz 13y ago
Coming from an EE background I remember lots of emphasis over the techniques for converting finite state machines into HDL code. For me, it's really cool to see the topic approached from the opposite direction, so to speak.
alexkus 13y ago
For my Comp Sci degree I wrote a regexp/automata library. It allowed you to create/modify/load/save/execute NFAs, and the same kinds of functions for a basic regexp language (character classes, ., Kleene star *, ?, etc) by first converting the regexp into an NFA (with epsilon transitions) as each regexp operation maps to a small NFA so they can be bolted together (with epsilon transitions). You could then (attempt to) convert NFAs into a DFA using Myhill-Nerode theorem to determinise it; I say attempt as it was possible to make it consume huge resources if you gave it the right/wrong kind of regexp. It also did minimisation and a few other bits and bobs. To say this gave me a good understanding of regular expressions is an understatement, and once you understand the basics then all of the parts of more complex regular expression languages become a lot easier! That was my enlightenment.
azov 13y ago
The answer on SE is still very theoretical. Yes, technically we can model any computation [1] as an FSM, but when does it actually make sense to do so? FSMs are often used when modelling physical devices - think microwaves, elevators, CD-players, something with buttons or sensors, something event-driven, embedded controllers, also network protocols, text parsers, etc. Basically, whenever we must ensure correct behavior having few constraints on sequence or timing of inputs. How can you actually apply it in your everyday programming? Look at your class. Every method call is an event that can cause a transition. Member variables are the state. Theoretically changing any bit of any member variable gives you a different state. In practice you only care about the bits that affect your control flow. Figuring out how variables map to states is the tricky part. Sometimes one variable corresponds to several states (say, when airspeed goes over V1 a plane transitions from can abort to must takeoff state), sometimes several variables define one state (say, when ignition=on and door=closed car is ready to drive), sometimes you'll need to add an extra variable to distinguish between states. Then you draw a table with events on one side and states on another and look at each cell. This is when you have all those precious "oh, crap, what if the user hits play when the song is already playing" moments. And voila - now you know that your class behaves correctly because you've systematically considered every possible scenario. It takes enough effort that you probably don't want to do it for each and every class, but when you do it - it's magic :-) [1] Any computation with finite memory, to be pedantic
- gwu78 13y ago
  This is a great comment. Thank you. I have had the opposite question from one posted to SE: What enlightenment will I attain when I can move beyond thinking of every solution in programming as a FSM? I have never understood the obsession with higher level languages with objects, classes, methods, etc. I can't seem to think beyond lex, regular expressions and case statements. You comment is reassuring. Maybe I'm already emlightened. And I just don't know it.
  - lmm 13y ago
    Encapsulation is what you're missing. OO programming only makes sense once you're working on a codebase too big to understand. I mean, I guess you could think of each object as its own FSM, but that's not particularly enlightening - in part because well designed objects don't have multiple possible states (rather, the state is captured in what they are. It's a hard notion to accept, like learning to use infinitesimals in mathematics - you've spent so long convincing yourself that this intuitive notion is wrong, and then suddenly you discover there's a way to make that intuitive notion correct after all, but you resist it because it seems like it's a messy, bad intuition). Yes, technically there are states to the whole system - but you need some way to factorize it into smaller systems if you're going to make any sense of it. There is a real enlightenment to be got from really understanding OO, and it's one that many supposedly good programmers seem never to reach. Keep seeking it.
MichaelMoser123 13y ago
I think the insight is that each formalism is defined by/equivalent to the input language that it is able to parse; State machines can do regular expressions, but they can't parse matching brackets, Stack machines can do BNF grammars - but they don't have counters; also Stack machines are more general than state machines; each regular expression can be expressed by an equivalent BNF grammar. Turing machines can parse Perl - that means any language that depends on the context; this is because Turing machines have counters/memory. Also Turing machines are more general than stack machines; each BNF grammar can also be parsed by a Turing machine. All this business of deterministic/non deterministic machines is about efficiency of the parser; nice to know.
segmondy 13y ago
Some problems are best solved using FA. Pac mac? Vending machine? ATM machine? Once you have the rules. You can be confident of no bugs.
bonemachine 13y ago
That nature computes (many, if not all natural processes can be thought of as computational in some respect), and that many computational systems can be thought of as at least analogs of physical or biological processes. See for example: http://www.uc09.uac.pt/JamesCrutchfield.php http://www.uc09.uac.pt/JamesCrutchfield.php

336 points by netvarun 13y ago

I'd say that finite automata give practical answers to many parsing problems which would be difficult otherwise.

I had come across this answer some time back, but got to revisit it again while reading another one of the author's (Vijay D. - http://www.eecs.berkeley.edu/~vijayd/#about http://www.eecs.berkeley.edu/~vijayd/#about ) answers trending on HN (https://news.ycombinator.com/item?id=6787836 https://news.ycombinator.com/item?id=6787836) Additional discussion: https://news.ycombinator.com/item?id=6788969 https://news.ycombinator.com/item?id=6788969

blibble 13y ago

on examinations of code it's normally pretty easy to see who has a formal understanding of state machines, and who doesn't.

sateesh 13y ago
Would you please elaborate. My experience has been that formal understanding of theory (say of state machines) equips one to handle complex problems and in no way indicates how well the code is written. For example, a GUI application code (say) making use of a framework wouldn't give any indication of whether the author had any formal understanding of state machines or not. In my opinion to write a good readable code one need not have a formal understanding of CS theory, but the understanding of CS theory is paramount in writing code for complex problems (say writing a compiler).
- blibble 13y ago
  7 booleans to try and maintain state instead of a single enum value happens quite a lot in my experience
- PeterisP 13y ago
  GUI application code actually is one that often can be very clearly thought as a DFA. In particular, the UI often is non-static and can be in certain states, with the effect of user actions (and possibility of certain actions) depending on that state. If it is implemented or "grown" ad-hoc, it sometimes may turn into a jumble of interdependent code and flag/visibility variables, but very often the exact same behaviour can be modelled and implemented much simpler if you think of it as a DFA. For example, the UI of recently popular single-page webapps, where JS is used to change 'screens' without page load, or change functionality by hiding/adding large parts of the page, can often be naturally be thought of as DFA, planned (on paper or wireframes) as states='screens' and transitions between them, and then implemented as DFA. Thinking of UI as a DFA also forces you to consider the 'proper' effect of every user action in every state, which is just good UX practice. For example, in a classic url-based web app you may draw a graph/process of how an user proceeds through making a purchase on your site. Usually it will include only the typical process - but if you think of it as a DFA, you define behavior for actions such as 'requested url /ordervalidation/step2-address' at every state, since the result likely should be different depending on if the user went there from step1 by clicking 'ok, i want to buy this', step3 by clicking the back button, or two weeks later by clicking on a link that he accidentally bookmarked.
tjgq 13y ago
Can you please elaborate?

raverbashing 13y ago

I have to say I am very happy with this discussion and the "data structures in the Linux Kernel" Such theoretical basis (and even their practical considerations) seems much more important than "What are the advantages of latest fad.js"

morganwilde 13y ago
I totally support this statement. Longterm thinking is based on first principles. [edit] Should be based on first principles.
- eruditely 13y ago
  This requires empirical support.
calt 13y ago
This post inspired me to up-vote. It's amazing how popular hacker news tends to be among the people I talk to but how few votes it can take to be on the front page.
mcphilip 13y ago
Agreed, with the caveat that I can only handle a couple of posts this deep before feeling intimidated and longing for something more lightweight. I like the mix of articles because if all of them were this deep it would feel like I don't belong here without years of prerequisite study.
manojlds 13y ago
Note that both the top answers are from the same person.

ape4 13y ago

What's the best book on this? (I'd prefer something non-academic)

sateesh 13y ago
Chapter 10 of the book "Foundations of Computer Science" (http://i.stanford.edu/~ullman/focs.html http://i.stanford.edu/~ullman/focs.html) which is available online provides an excellent introduction to automata theory. After that you can start referring to " Introduction to Automata Theory, Languages, and Computation" by Ullman, Hopcraft and Motwani. This is also the reference book for the Automata course (and taught by Ullman) currently being available in Coursera.
tomstuart 13y ago
I wrote a non-academic book on this subject for the HN crowd: http://computationbook.com/ http://computationbook.com/
justin66 13y ago
I took a quick look at Tom Stuart's book and it looks great (thanks for sharing that, Tom! something new on my reading list). Somewhere in between that and Ullman's stuff in terms of formality is Sipser's Introduction to the Theory of Computation. I like its explanations of the DFA material more than the free Ullman book online, though I haven't read Ullman's dedicated Automata title. (A little too rich for my blood...)

diminish 13y ago

If you're interested in learning Automata from Prof. Jeff Ullman of Stanford you may join the current session on Coursera. What's best about this course is that Prof. Ullman is always present in discussion forums, and helps everyone learn and enjoy great discussions. Join here https://www.coursera.org/course/automata https://www.coursera.org/course/automata Edit: I'm currently learning there, and enjoy it a lot. Especially in video 6, you may listen to the stories of Junglee startup, Started in the mid-90’s by three of his students, Ashish Gupta, Anand Rajaraman, and Venky Harinarayan. Goal was to integrate information from Web pages. Bought by Amazon when Yahoo! hired them to build a comparison shopper for books. They made extensive use of regular expressions to scrap..."

brudgers 13y ago
The Coursera Automata course is awesome. Ullman's active participation in the current second offering is part of it. But what really makes the course for me is that Ullman's presentations are relaxed. He knows the material, he knows where various aspects of the material rank in terms of importance to the learner, he has a feel for where students will get hung up, and he has no need to prove anything. Ultimately, this gives the class the feel of a graduate seminar. It is designed so that student's can readily succeed in learning the material rather than structured around the idea of weeding out weaker students. It assumes that anyone who wants to learn the material can with enough effort, and that that learning is really all that matters.
- sateesh 13y ago
  In addition to the lectures what has made the course interesting to me is the vibrant, active "Discussion Forum" associated with this course. Ullman himself frequently posts explanation on some of the topics here. It seems there are some takers of this course who are well versed with Automata theory. Some of them are quite active in the discussion forum providing good explanation to many of the trickier concepts introduced in the course (which has been immensely valuable to me).
  - brudgers 13y ago

knicholes 13y ago

Oh yeah-- Without studying finite automata, writing my compiler would have sucked. [edited] would have sucked even more

en4bz 13y ago

I originally went into my Theory of Computation class this year grunting and moaning about it was a waste of time and how I would rather be writing actually software. Now I actually kind of enjoy the class and can see its use. I find the discussion on Decidability to probably be one of the most important part. Although it's a little disappointing to find out that there are some problems that we will never be able to solve.

robdd 13y ago

ROBDD: Reduced Ordered Binary Decision Diagram A flow chart with a truth table, which is used to map all of the possible ways to arrive at one or zero by carrying out a set of steps, which may follow recursive paths, such that the similarities of different paths to identical outcomes can be better understood. Where ( reduced = all roads lead to one or zero ) and ( ordered = applying good organization to the steps of the decisions in the flow chart, even when steps in the decision tree can be carried out in a variety of ways )

itistoday2 13y ago

I didn't study finite automata at school, but I studied cellular automata on my own. If anyone would like to describe the difference (if there is one), it'd be appreciated. W.r.t cellular automata, I made this video, and if this isn't enlightenment, I don't know what is: https://vimeo.com/80147310 https://vimeo.com/80147310

theseoafs 13y ago
Cellular automata are one of the things you study in automata theory, which is the study of different models of computation. Although cellular automata are of some interest (Game of Life is Turing-complete, etc.), I wouldn't say they're nearly as important as the other models of computation you'd study in a normal undergraduate class (DFA's/NFA's, PDA's, Turing Machines).
- itistoday2 13y ago
  Thanks! Much obliged for the explanation (and damn anyone who downvotes me for an expression of gratitude!).

t1m 13y ago

New appreciation for the goto statement.

Confusion 13y ago

The link does not answer the question. The answer is: there is no enlightenment you're supposed to attain immediately after studying finite automata. You've created the possibility for enlightenment further down the road. Studying finite automata equips you with a bunch of knowledge about their behavior, which equips you with a bunch of knowledge about the behavior of a variety of other subjects, because they can be projected onto automata (can be reduced to automata, can be morphed into automata, ...). The link lists a bunch of properties of, and relations between, various kinds of FA's and explains how these are useful to other areas of CS and even to regular programming. But you cannot be expected to have these thoughts as sudden epiphanies. At most you can at a later time realize a certain property exists, realize the same property exists for FA's and realize that makes sense, because of the relation between your subject and FA's. You can then further realize that you know immediately know a lot more about the subject as well. Some of these realizations may strike you with a physically tingling sensation of aesthetically pleasantness which some call 'enlightenment', but YMMV.

andrewflnr 13y ago
The question did not stipulate an "immediate" enlightenment. If that's what you wanted fine, but the question as asked was answered just fine.

lindig 13y ago

You might realise that parsing HTML or C with regular expressions is a bad idea.

laureny 13y ago
Really? http://stackoverflow.com/a/1732454/162410 http://stackoverflow.com/a/1732454/162410
UNIXgod 13y ago
It's tricky with HTML but can be done. The C language was one of it's initial use cases.
- theseoafs 13y ago
  No, it can't. As in, you cannot parse HTML or C with regular expressions, and you can prove that that's the case. Regexes simply aren't powerful enough. This is one of the advantages of studying formal languages -- you get to learn about really useful models of computation (here, DFA's), but you also get to learn about their limits.
- dllthomas 13y ago
  Scanning the C language is done using regular expressions, typically. Parsing the resulting token stream cannot be done with only regular expressions. At least not with the theoretical construct. Some "regular expressions" libraries, notably PCRE, let you do plenty that goes beyond the theory at the expense of some efficiency. Parsing some context-free grammars with these libraries is certainly possible, but you're not really restricting yourself to "just" regular expressions at that point. Regular expressions plus interwoven use of a stack is a pushdown-automata, which can totally parse C and HTML.
dllthomas 13y ago
Parsing C or HTML with regular expressions is a great idea. Parsing C or HTML with only regular expressions isn't.

mrottenkolber 13y ago

I'd say after learning about different classes of automata, you should understand what a compiler does in general. At least, that's what I took from it.

chubot 13y ago

A modern processor has a lot in it, but you can understand it as a finite automaton. Just this realisation made computer architecture and processor design far less intimidating to me. It also shows that, in practice, if you structure and manipulate your states carefully, you can get very far with finite automata. I don't understand this one. Surely a modern processor is like a Turing machine and not a finite state automata. For example, a DFA/NFA can't express simple algorithms like matching parentheses, while obviously a modern processor can.

loup-vaillant 13y ago
The processor plus the RAM is a Turing machine. If you decide in advance what input go to the input pins, regardless of the output, and you just record what goes out the output pins, the processor is pretty much a DFA. When you add the RAM, you provide a feedback loop: input depends on previous outputs (in plainspeak, when you write to the RAM, you can read it later). No feedback loop, no Turing machine.
andrewaylett 13y ago
It's basically because you don't have infinite storage -- I could, given enough time, feed your PC a string that it wouldn't be able to tell was unbalanced. Of course, to do that I would have to overflow your available storage which would take a while. For all practical purposes, your PC adequately models a Turing machine. In point of literal fact, it doesn't because it only has finite storage. In practical usage, it is sometimes helpful to consider various states your code may enter and how they interact. For understanding how the system actually works, the author appears to have found the state-switching model to be a useful one, and indeed I understand that it's common to model the internal state of various devices using finite automata.
- chas 13y ago
  A PC can still read and write from arbitrary memory locations which means it can know a lot about it's past states, so the memory limit makes it a deterministic linear-bounded automata. http://en.wikipedia.org/wiki/Linear_bounded_automaton http://en.wikipedia.org/wiki/Linear_bounded_automaton

undoware 13y ago

...cannot be played on record player B.

Adrock 13y ago

The list in the 1st answer is amazing, but the 2nd highest answer has one of my favorite things: > Turing machines (we think) capture everything that's computable. However, we can ask: What parts of a Turing machine are "essential"? What happens when you limit a Turing machine in various ways? DFAs are a very severe and natural limitation (taking away memory). PDAs are a less severe limitation, etc. It's theoretically interesting to see what memory gives you and what happens when you go without it. It seems a very natural and basic question to me. I like to think of it the other way, though. A DFA with a stack is a PDA. A DFA with two stacks is a Turing machine. Looking at the 3 different classes as DFAs with 0, 1, or 2 stacks is just so beautiful...

alok-g 13y ago
Adding to the above: While in most algorithms books, we treat integer operations (addition, multiplication) as an O[1] operation, most do not even mention that this is only because these integers are constrained in size to a limited number of bits. Storing an integer in mathematics would require infinite amount of memory. Analyzing the Big-O complexity of the algorithms is too much more fun when you take the integer fixed-width assumption out. A single integer can serve as a "stack" from the perspectives of computer science. Without loss of generalization, assume that the set of symbols has digits 1..9. Now push operation is multiplication by ten and addition of the digit, while pop is taking the units digit and dividing by ten. In other words, if you are using a single integer in your program, and do not want to simply return incorrect answers or throw exceptions due to overflow errors, then your algorithm may already be beyond an NDFA. This would for example happen if you are trying to match parenthesis in a string like "(()())(((())))". You can easily do this by having an integer in your program, reading the string from left to right, incrementing the integer when you encounter a '(' and decrement for a ')'. The computer science books would however show the above problem to be unsolvable using a NDFA. (You have solved the problem for all practical purposes since the strings you'll encounter may never be that long, but a computer with finite memory is in principle incapable of solving this "correctly" for all possible inputs.)
SandyPark 13y ago
How is a Turing Machine a DFA with two stacks? I never learned it like that in my Theory of Computation course...

jmount 13y ago

Suffix Trees. That kind of hyper efficient recognition is even harder to think about without the finite automata theory behind regular expressions.

crb002 13y ago
I posted this above. Micron is releasing a new NFA card http://www.micron.com/about/innovations/automata-processing http://www.micron.com/about/innovations/automata-processing Any guess on which formerly expensive NFA algorithms will be put to use on it in short order?

crb002 13y ago

This. Micron's in memory automata is going to eat your lunch on many algorithms. Bye bye Van Neuman bottleneck. http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CC8QFjAA&url=http%3A%2F%2Fwww.micron.com%2F~%2Fmedia%2FDocuments%2FProducts%2FOther%2520Documents%2Fautomata_processing_technical_paper.pdf&ei=yj-SUqTUKdLtqQH_4YGYAg&usg=AFQjCNH9ikjKujCHM2h-10UN-9puwIx1qw&sig2=Fdv6xqQFXWM2Jlk1kQ4s1g&bvm=bv.56988011,d.aWM http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd...

crb002 13y ago
Press release: http://www.micron.com/about/innovations/automata-processing http://www.micron.com/about/innovations/automata-processing

GhotiFish 13y ago

>Turing machines (we think) capture everything that's computable. ?? eh?! we think? Isn't the definition of computable, "something that can be reached by a Turing machine?"

Grothendieck 13y ago
There's good evidence that Turing machines do capture the right notion of computability. You can enhance a Turing machine in many ways without changing what it can compute. Further, Turing machines, the lambda calculus, recursive functions, cellular automata, and register machines all give the same notion. Even a quantum computer can be simulated by a Turing machine. https://en.wikipedia.org/wiki/Church-turing_thesis https://en.wikipedia.org/wiki/Church-turing_thesis
argv_empty 13y ago
That's the definition when "computable" is used in a formal setting. What we believe is that it is also equivalent to our informal, intuitive understanding of the term.

austinz 13y ago

Coming from an EE background I remember lots of emphasis over the techniques for converting finite state machines into HDL code. For me, it's really cool to see the topic approached from the opposite direction, so to speak.

alexkus 13y ago

For my Comp Sci degree I wrote a regexp/automata library. It allowed you to create/modify/load/save/execute NFAs, and the same kinds of functions for a basic regexp language (character classes, ., Kleene star *, ?, etc) by first converting the regexp into an NFA (with epsilon transitions) as each regexp operation maps to a small NFA so they can be bolted together (with epsilon transitions). You could then (attempt to) convert NFAs into a DFA using Myhill-Nerode theorem to determinise it; I say attempt as it was possible to make it consume huge resources if you gave it the right/wrong kind of regexp. It also did minimisation and a few other bits and bobs. To say this gave me a good understanding of regular expressions is an understatement, and once you understand the basics then all of the parts of more complex regular expression languages become a lot easier! That was my enlightenment.

azov 13y ago

The answer on SE is still very theoretical. Yes, technically we can model any computation [1] as an FSM, but when does it actually make sense to do so? FSMs are often used when modelling physical devices - think microwaves, elevators, CD-players, something with buttons or sensors, something event-driven, embedded controllers, also network protocols, text parsers, etc. Basically, whenever we must ensure correct behavior having few constraints on sequence or timing of inputs. How can you actually apply it in your everyday programming? Look at your class. Every method call is an event that can cause a transition. Member variables are the state. Theoretically changing any bit of any member variable gives you a different state. In practice you only care about the bits that affect your control flow. Figuring out how variables map to states is the tricky part. Sometimes one variable corresponds to several states (say, when airspeed goes over V1 a plane transitions from can abort to must takeoff state), sometimes several variables define one state (say, when ignition=on and door=closed car is ready to drive), sometimes you'll need to add an extra variable to distinguish between states. Then you draw a table with events on one side and states on another and look at each cell. This is when you have all those precious "oh, crap, what if the user hits play when the song is already playing" moments. And voila - now you know that your class behaves correctly because you've systematically considered every possible scenario. It takes enough effort that you probably don't want to do it for each and every class, but when you do it - it's magic :-) [1] Any computation with finite memory, to be pedantic

gwu78 13y ago
This is a great comment. Thank you. I have had the opposite question from one posted to SE: What enlightenment will I attain when I can move beyond thinking of every solution in programming as a FSM? I have never understood the obsession with higher level languages with objects, classes, methods, etc. I can't seem to think beyond lex, regular expressions and case statements. You comment is reassuring. Maybe I'm already emlightened. And I just don't know it.
- lmm 13y ago
  Encapsulation is what you're missing. OO programming only makes sense once you're working on a codebase too big to understand. I mean, I guess you could think of each object as its own FSM, but that's not particularly enlightening - in part because well designed objects don't have multiple possible states (rather, the state is captured in what they are. It's a hard notion to accept, like learning to use infinitesimals in mathematics - you've spent so long convincing yourself that this intuitive notion is wrong, and then suddenly you discover there's a way to make that intuitive notion correct after all, but you resist it because it seems like it's a messy, bad intuition). Yes, technically there are states to the whole system - but you need some way to factorize it into smaller systems if you're going to make any sense of it. There is a real enlightenment to be got from really understanding OO, and it's one that many supposedly good programmers seem never to reach. Keep seeking it.

MichaelMoser123 13y ago

I think the insight is that each formalism is defined by/equivalent to the input language that it is able to parse; State machines can do regular expressions, but they can't parse matching brackets, Stack machines can do BNF grammars - but they don't have counters; also Stack machines are more general than state machines; each regular expression can be expressed by an equivalent BNF grammar. Turing machines can parse Perl - that means any language that depends on the context; this is because Turing machines have counters/memory. Also Turing machines are more general than stack machines; each BNF grammar can also be parsed by a Turing machine. All this business of deterministic/non deterministic machines is about efficiency of the parser; nice to know.

segmondy 13y ago

Some problems are best solved using FA. Pac mac? Vending machine? ATM machine? Once you have the rules. You can be confident of no bugs.

bonemachine 13y ago

That nature computes (many, if not all natural processes can be thought of as computational in some respect), and that many computational systems can be thought of as at least analogs of physical or biological processes. See for example: http://www.uc09.uac.pt/JamesCrutchfield.php http://www.uc09.uac.pt/JamesCrutchfield.php