HiveBrain v1.2.0
Get Started
← Back to all entries
patternCritical

Why is English not a regular language?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whyenglishregularlanguagenot

Problem

Surely any language with a finite longest word can be made regular by having an automaton with paths to 26 states for all letters and then having each of those states go to another 26 states, etc., with states going to a looping non-final state whenever there are no possible words to be made beginning with the letters you have already gone through. Then make every state that ends on a word final.

Solution

The English language is regular if you consider it as a set of single words. However, English is more than a set of words in a dictionary. English grammar is the non-regular part. Given a paragraph, there is no DFA deciding whether it is a well-written paragraph in the English language. Of course, it can say whether each word is an English word or not, but it can not judge whole paragraphs.

Context

StackExchange Computer Science Q#116127, answer score: 55

Revisions (0)

No revisions yet.