Hacker News Reader

Comment by netvarun | Hacker News Reader

On a (slightly) related note, you should also check out the author Vijay's (http://www.eecs.berkeley.edu/~vijayd/#about) answer on the benefits of learning Finite Automata: http://cstheory.stackexchange.com/questions/14811/what-is-th...

View on HN

Its overall a very good post, although WRT response #9 and #22 of his answer its surprising no one mentions the venn diagram-like effect where its very easy for (real) CS types to solve problems using regex and e-NFAs and all that higher level stuff and the point of the class is teaching how to convert from one form to another. Also its really easy for EE types to implement any DFA using a vast pile of flipflops and logic gates of various types in a simple scalable algorithmic-ish way that doesn't really exist (at least as a simple algo) for converting e-NFAs into NAND gates or whatever. That intersection of those two areas is where the assemblers, interpreters, compilers, disassemblers, and their close buddies all live.

So this whole e-NFA / NFA / DFA / regex topic is at least one provably complete way you can translate from 'ls *.html' into a whole bunch of gates and FFs in hardware.

There are of course usually ways a smart-ish human can make a faster less general more specific hardware implementation. But its real handy for language designers etc to know that based on CS theory its impossible to write a regex that can't, eventually, be turned into operating hardware.

Now you can add features to regex until you screw that up, if you try hard enough, but I can't think of any good examples at this time. And not all added features screw it up either, some pretty obvious syntactic sugar homomorphisms don't do anything other than make regexes easier for humans to write and understand.

There are standard examples where the minimal deterministic automaton for a language is exponentially larger than a minimal non-deterministic automaton

Can anyone provide one such example, please?

"the language of strings over the alphabet {0,1} in which there are at least n characters, the nth from last of which is 1. It can be represented by an (n + 1)-state NFA, but it requires 2n DFA states, one for each n-character suffix of the input."

http://en.wikipedia.org/wiki/Powerset_construction#Complexit...

For reference, that "2n" is supposed to be 2^n.

Thanks for catching that.

Reply on news.ycombinator.com