A colleague asked me an interesting question recently:
Can the Chomsky hierarchy (regular grammars, context-free, context-sensitive, Turing-complete) be phrased in terms that functional programmers would find natural, e.g. in terms of typed or syntactically restricted lambda-calculi?
Pointers appreciated...
- Benjamin