World's most popular travel blog for travel bloggers.

[Solved]: Proving that English is not a regular language

, , No Comments
Problem Detail: 

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?

Asked By : user3295674

Answered By : Shreesh

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback