News for hackers. Stuff that matters.
Re:What is the enlightenment I'm supposed to attain after st... by MichaelMoser123 on Sunday November 24, 2013 @06:25PM (#6791648)
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.

There are no comments on this comment yet.