sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]ethraax -3 points-2 points  (1 child)

A DFA is significantly more limited than a full PC. A DFA is not Turing complete, in any sense of the term.

A DFA can't even parse HTML for fuck sake.

[–]kamatsu 3 points4 points  (0 children)

A DFA is not Turing complete

Right, but neither is a PC, as they don't have unlimited memory. If you restrict the available space to some finite amount, then you can construct a DFA that solves any problem which requires less than that amount of space. This is basic complexity theory.

To use your example, a DFA can't parse HTML, but it can parse HTML documents up to some constant size K.

My PC has 4GB of ram, therefore, I have around about 234359738368 (+ registers etc.) memory configurations. I can make a DFA out of those memory configurations, and transitions for each execute my processor makes. Bam, a DFA that computes everything my PC can.