# Examples for CFG that cannot be expressed by regular language

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!

• What is a contrivation? – Hans Hüttel May 26 '17 at 20:50

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. I refer to the seminal papers 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, in general, the "cognitive" system could not handle them, or said differently this could be conceived as a finite state systems. I refer, for example, to the famous paper The magical number seven, plus or minus two by G. Miller, which states that for numbers the human brain can only 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.

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.