3
$\begingroup$

There are nice examples for context free grammars which cannot be expressed with regular language, for example the palindrome and a similar contrived example here, but they are very intuitively applicable for formal languages, e.g. checking for balanced nested parentheses and such.

Can you conceive an example that is pertinent to natural languages?

Part of the motivation to this question is that in one view, regular expressions are practically intractable when it comes to combining and scaling them to describe natural language phenomena; they don't compose as nicely as grammars. But at the same time I can't easily think of an actual example where regular expressions should not be enough for describing natural languages.

An example, therefore, for some natural language phenomena that cannot be modelled with regular language, would be very nice and interesting!

$\endgroup$
  • $\begingroup$ What is a contrivation? $\endgroup$ – Hans Hüttel May 26 '17 at 20:50
3
$\begingroup$

Theoretically, you can nest sentences arbitrarily depth, by using subclauses and this excluded any finite state mechanism. The inventor of the phrase structure grammars himself looked at finite state languages, and compared them with the model of phrase structure grammars. The abstract of his paper Finite State languages reads:

We find that no finite-state Markov-process [...] can serve as an English grammar [...]

The idea to use finite Markov processes, which came down to finite automata in Chomskys work, go back to ideas of Shannon (see his seminal work A mathematical theory of communication). If this caught your interest, you might also take a look at the two works Three models for the description of language and Syntactic structures by N. Chomsky, where he further discusses the adequacy of grammars and finite state processes for language description (or production thereof).

Later, these ideas which originally came from linguistics, and where therefore closely related to research on natural languages, where later adapted by computer scientists to describe programming languages, see the paper Two families of languages related to ALGOL by Ginsburg and Rice, or Revised Report on the Algorithmic Language Algol 60 where the BNF was introduced, the first papers using this phrase structure (or nowadays context free grammars) to describe programming languages.

But on the other side, you seldom find "arbitrary" complex nested sentences, as your "cognitive" system would not handle them, or said differently this could be conceived as a finite state systems, see for example the famous paper The magical number seven, plus or minus two by G. Miller which states roughly that for numbers the human brain can just store a finite number $7 \pm 2$ of digits. Similar restrictions might hold for language processing, see the textbook The psychology of language by T. Harley where these issues are discussed.

$\endgroup$
2
$\begingroup$

If no bracket language examples suffice, your quest is futile. Every context-free-language is a reduction of a bracket/parenthesis language. Reduction comprises

  • homomorphism;
  • intersection with a regular language.

This is the Chomsky-Schutzenberger (representation) theorem.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.