One can have a look on the Chomsky hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy , especially the inset named "Automata theory: formal languages and formal grammars" at the bottom of the page. When one tries to model natural language (e.g. as http://www.grammaticalframework.org/ tries to do it), then one usually aims for the most expressive formal language that is still decidable and recursive languages are exactly such languages - they are the most expressive decidable languages. But GrammaticalFramework instead narrows the scope and uses the mildly context-sensitive language instead for doing its modelling. Why it is so? Why one elaborates the hierarchy of languages, what compromises he or she tries to make?

As far as I understand from my studies, then the complexity issue is the single most important issue. One can try to use recursive language, but recognition and parsing of such languages are very slow. Or maybe there are different reasons? Maybe there are not even algorithms how convert recursive language into total Turing machine (and vice versa) or maybe there are not even algorithms for the parsing of recursive language. So - why not to use recusive language? Due to lack of algorithms? Or due to nonpolynomial/exponential complexities of those algorithms? And that is why the hierarchy is so elaborated - one can try to find the most expressible language with the best complexity properties.

It is somehow different with logics. In logics one can tolerate the complexity issue and one is required to make compromises between expressibility and decidability. For recursive languages the recognition is decidable and so one should seek compromises between expressibility and complexity. Am I right?

The key point of my question is this: what obstacles prevent the practical use of recursive languages and why one is required to elaborate hierarchy of languages and to use less expressive languages? Complexity? Lack of algorithms? Something different?

  • $\begingroup$ Just in case you are not aware, a continual trend considers the Chomsky hierarchy is so coarse or inappropriate that we need to come up with various new classes of languages to see if they will model natural languages better. $\endgroup$ – John L. Jan 2 '19 at 23:23
  • 1
    $\begingroup$ Parsing in polynomial time has been one of the central requirements for formalisms modelling natural language. Exponential time is thought to be too much even for the human brain, That is why the recursive and also the context.sensitive languages are not considered good models. For the mildly context-sensitive models polynomila time parsing is one of the central requirements. $\endgroup$ – Peter Leupold Jan 3 '19 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.