TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

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

336 点作者 netvarun超过 11 年前

26 条评论

raverbashing超过 11 年前
I have to say I am very happy with this discussion and the &quot;data structures in the Linux Kernel&quot;<p>Such theoretical basis (and even their practical considerations) seems much more important than &quot;What are the advantages of latest fad.js&quot;
评论 #6789994 未加载
评论 #6789953 未加载
评论 #6789963 未加载
评论 #6790251 未加载
azov超过 11 年前
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?<p>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.<p>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 <i>can abort</i> to <i>must takeoff</i> state), sometimes several variables define one state (say, when ignition=on and door=closed car is <i>ready to drive</i>), sometimes you&#x27;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 &quot;oh, crap, what if the user hits <i>play</i> when the song is already playing&quot; moments. And voila - now you know that your class behaves correctly because you&#x27;ve systematically considered every possible scenario. It takes enough effort that you probably don&#x27;t want to do it for each and every class, but when you do it - it&#x27;s magic :-)<p>[1] Any computation with finite memory, to be pedantic
评论 #6792453 未加载
评论 #6793091 未加载
Confusion超过 11 年前
The link does not answer the question. The answer is: there is no enlightenment you&#x27;re supposed to attain immediately after studying finite automata. You&#x27;ve created the possibility for enlightenment further down the road.<p>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, ...).<p>The link lists a bunch of properties of, and relations between, various kinds of FA&#x27;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&#x27;s and realize that makes sense, because of the relation between your subject and FA&#x27;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 &#x27;enlightenment&#x27;, but YMMV.
评论 #6791521 未加载
Adrock超过 11 年前
The list in the 1st answer is amazing, but the 2nd highest answer has one of my favorite things:<p>&gt; Turing machines (we think) capture everything that&#x27;s computable. However, we can ask: What parts of a Turing machine are &quot;essential&quot;? 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&#x27;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.<p>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...
评论 #6790429 未加载
评论 #6790491 未加载
diminish超过 11 年前
If you&#x27;re interested in learning Automata from Prof. Jeff Ullman of Stanford you may join the current session on Coursera. What&#x27;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 <a href="https://www.coursera.org/course/automata" rel="nofollow">https:&#x2F;&#x2F;www.coursera.org&#x2F;course&#x2F;automata</a><p>Edit: I&#x27;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...&quot;
评论 #6789896 未加载
评论 #6790095 未加载
alexkus超过 11 年前
For my Comp Sci degree I wrote a regexp&#x2F;automata library. It allowed you to create&#x2F;modify&#x2F;load&#x2F;save&#x2F;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).<p>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&#x2F;wrong kind of regexp. It also did minimisation and a few other bits and bobs.<p>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.
netvarun超过 11 年前
I had come across this answer some time back, but got to revisit it again while reading another one of the author&#x27;s (Vijay D. - <a href="http://www.eecs.berkeley.edu/~vijayd/#about" rel="nofollow">http:&#x2F;&#x2F;www.eecs.berkeley.edu&#x2F;~vijayd&#x2F;#about</a> ) answers trending on HN (<a href="https://news.ycombinator.com/item?id=6787836" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=6787836</a>)<p>Additional discussion: <a href="https://news.ycombinator.com/item?id=6788969" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=6788969</a>
en4bz超过 11 年前
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&#x27;s a little disappointing to find out that there are some problems that we will never be able to solve.
austinz超过 11 年前
Coming from an EE background I remember lots of emphasis over the techniques for converting finite state machines into HDL code. For me, it&#x27;s really cool to see the topic approached from the opposite direction, so to speak.
crb002超过 11 年前
This. Micron&#x27;s in memory automata is going to eat your lunch on many algorithms. Bye bye Van Neuman bottleneck. <a href="http://www.google.com/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=1&amp;ved=0CC8QFjAA&amp;url=http%3A%2F%2Fwww.micron.com%2F~%2Fmedia%2FDocuments%2FProducts%2FOther%2520Documents%2Fautomata_processing_technical_paper.pdf&amp;ei=yj-SUqTUKdLtqQH_4YGYAg&amp;usg=AFQjCNH9ikjKujCHM2h-10UN-9puwIx1qw&amp;sig2=Fdv6xqQFXWM2Jlk1kQ4s1g&amp;bvm=bv.56988011,d.aWM" rel="nofollow">http:&#x2F;&#x2F;www.google.com&#x2F;url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd...</a>
评论 #6790412 未加载
robdd超过 11 年前
ROBDD: Reduced Ordered Binary Decision Diagram<p>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.<p>Where (<p><pre><code> reduced = all roads lead to one or zero </code></pre> ) and (<p><pre><code> 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 )</code></pre>
PaulHoule超过 11 年前
I&#x27;d say that finite automata give practical answers to many parsing problems which would be difficult otherwise.
chubot超过 11 年前
<i>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><p>I don&#x27;t understand this one. Surely a modern processor is like a Turing machine and not a finite state automata. For example, a DFA&#x2F;NFA can&#x27;t express simple algorithms like matching parentheses, while obviously a modern processor can.
评论 #6790404 未加载
评论 #6791619 未加载
评论 #6791570 未加载
knicholes超过 11 年前
Oh yeah-- Without studying finite automata, writing my compiler would have sucked.<p>[edited] would have sucked even more
lindig超过 11 年前
You might realise that parsing HTML or C with regular expressions is a bad idea.
评论 #6790676 未加载
评论 #6790043 未加载
评论 #6790087 未加载
MichaelMoser123超过 11 年前
I think the insight is that each formalism is defined by&#x2F;equivalent to the input language that it is able to parse;<p>State machines can do regular expressions, but they can&#x27;t parse matching brackets,<p>Stack machines can do BNF grammars - but they don&#x27;t have counters; also Stack machines are more general than state machines; each regular expression can be expressed by an equivalent BNF grammar.<p>Turing machines can parse Perl - that means any language that depends on the context; this is because Turing machines have counters&#x2F;memory. Also Turing machines are more general than stack machines; each BNF grammar can also be parsed by a Turing machine.<p>All this business of deterministic&#x2F;non deterministic machines is about efficiency of the parser; nice to know.
blibble超过 11 年前
on examinations of code it&#x27;s normally pretty easy to see who has a formal understanding of state machines, and who doesn&#x27;t.
评论 #6789982 未加载
评论 #6790176 未加载
ape4超过 11 年前
What&#x27;s the best book on this? (I&#x27;d prefer something non-academic)
评论 #6789904 未加载
评论 #6790859 未加载
评论 #6791470 未加载
t1m超过 11 年前
New appreciation for the goto statement.
bonemachine超过 11 年前
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.<p>See for example: <a href="http://www.uc09.uac.pt/JamesCrutchfield.php" rel="nofollow">http:&#x2F;&#x2F;www.uc09.uac.pt&#x2F;JamesCrutchfield.php</a>
mrottenkolber超过 11 年前
I&#x27;d say after learning about different classes of automata, you should understand what a compiler does in general. At least, that&#x27;s what I took from it.
segmondy超过 11 年前
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.
GhotiFish超过 11 年前
&gt;Turing machines (we think) capture everything that&#x27;s computable.<p>??<p>eh?! we think?<p>Isn&#x27;t the definition of computable, &quot;something that can be reached by a Turing machine?&quot;
评论 #6790593 未加载
评论 #6794878 未加载
undoware超过 11 年前
...cannot be played on record player B.
jmount超过 11 年前
Suffix Trees. That kind of hyper efficient recognition is even harder to think about without the finite automata theory behind regular expressions.
评论 #6790617 未加载
itistoday2超过 11 年前
I didn&#x27;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&#x27;d be appreciated.<p>W.r.t cellular automata, I made this video, and if this isn&#x27;t enlightenment, I don&#x27;t know what is: <a href="https://vimeo.com/80147310" rel="nofollow">https:&#x2F;&#x2F;vimeo.com&#x2F;80147310</a>
评论 #6790666 未加载