14 Apr
2002
14 Apr
'02
6:37 p.m.
In message <E16wOlk-0000BS-00(a)leng.cold.waste>te>, Thilo Schmidt writes:
To get the hierarchy ("<=>" means
equivalent):
FSMs <=> regular languages <=> primitive recursive functions
PDAs <=> context free languages <=> partial recursive functions
Turing Machines <=> context sensitive languages <=> computable functions
One quibble:
Linearly bounded automata <=> context sensitive languages
Turing Machines <=> phrase structured languages
Of course, if you want to get exotic, there's probabilistic
automata. Throw in rules for creating new states and
updating probabilities based on experience and you've
got the machine learning research in my dissertation.
Brian L. Stuart