I am wanting to try and prove that the English language is not regular. The alphabet is the set of all words in the English dictionary.

Looking at sentences, I was able to use this pattern of sentences

{ [ (determiner) (noun)]n (verb)n where n is >= 1} ⊆ of the English language

and { [ (determiner) (noun)]m (verb)n where m ≠ n} ∩ of English

determiner is anything like the, my etc. Noun is any noun and verb is also any verb.

All three of these (determiner, noun, and verb) are finite and disjoint. Would something like pumping lemma be a good way to approach this?

  • 1
    $\begingroup$ Are you after English as a formal language, or English as spoken? It's probably trivial to give a proof for the former (there's bound to be well-nested parentheses somewhere in English) but the language as used is probably finite, hence regular. $\endgroup$ – Raphael Feb 16 '16 at 10:50

It is not easy to prove the complexities of natural languages. See Complexity of natural languages for some hint that English language is not regular.

In fact in Evidence Against the Context-Freeness of Natural Language, Stuart M. Shieber shows that many natural languages are not even context-free.

However, I only know about Dutch and a dialect of Swiss German, for which proof of non context-freeness exists. And the proofs are quite old, the results about them were proved in 1980s.

For detail you can also refer - The Handbook of Computational Linguistics and Natural Language Processing edited by Alexander Clark, Chris Fox, Shalom Lappin.


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.