3 ms·
Regular expressions = regular languages. Stack machines = context free languages = primitive recursive functions. (?) Turingmachines = context sensitive lang
by mcguire 10y ago
Regular expressions = regular languages.
Stack machines = context free languages = primitive recursive functions. (?)
Turingmachines = context sensitive languages = total recursive functions. (?)
Or something like that.
- thesz 10y agoYou are wrong. Primitive recursive functions alone are able to recognize formal languages: https://en.wikipedia.org/wiki/PR_(complexity) https://en.wikipedia.org/wiki/PR_(complexity) PR is the complexity class of all primitive recursive functions—or, equivalently, the set of all formal languages that can be decided by such a function.