22
$\begingroup$

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.

$\endgroup$
  • 44
    $\begingroup$ Because "English is really three languages stacked up wearing a trenchcoat" ? $\endgroup$ – Criggie Oct 23 at 3:22
  • 5
    $\begingroup$ Are other human languages regular? I mean, is there a reason you picked out English other than we're using it here? $\endgroup$ – user3445853 Oct 23 at 10:07
  • 4
    $\begingroup$ Some people say there are infinitely many English words: e.g. we can have an argument, a counterargument, a counter-counterargument, a counter-counter-counterargument, ... $\endgroup$ – reinierpost Oct 23 at 16:16
  • 2
    $\begingroup$ @Criggie: Three? More like several dozen and counting. $\endgroup$ – Sean Oct 23 at 22:45
  • 2
    $\begingroup$ @reinierpost At least that one is regular! $\endgroup$ – user253751 Oct 24 at 8:41
52
$\begingroup$

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.

$\endgroup$
  • 41
    $\begingroup$ In particular, the standard example is that you can build sentences of the form "the mouse escaped", "the mouse the cat chased escaped", "the mouse the cat the man owned chased escaped" that are grammatical and are arbitrarily long. These are similar to the language of matched parentheses "()", "(())" etc., and hence irregular for the same reasons. $\endgroup$ – rlms Oct 22 at 20:04
  • 11
    $\begingroup$ However we can't conclude that English is irregular just from the fact that it has an irregular subset (for instance the language of all strings of parentheses does too, but that's clearly regular). The valid argument comes from the fact that all grammatical English strings of the form "(the [noun])*[verb]*" have matching numbers of nouns and verbs. $\endgroup$ – rlms Oct 22 at 20:05
  • 4
    $\begingroup$ @Richard Clearly a sentence can't have infinite words, but how sure are you about an upper limit? I wouldn't be so sure that such a limit exists. $\endgroup$ – kutschkem Oct 23 at 7:43
  • 5
    $\begingroup$ @kutschkem There are an infinite number of sentences. Each sentence is finite, but there are an infinite number of them. Like the prime numbers: each one is finite, but there are an infinite number of them. $\endgroup$ – user253751 Oct 23 at 8:35
  • 3
    $\begingroup$ Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo $\endgroup$ – JimmyJames Oct 23 at 14:17
14
$\begingroup$

Expansion of my comments to narek Bojikian's answer:

When people talk about natural languages such as English not being regular, they're usually talking on the level of grammar (syntax) rather than individual words. For instance, English has centre embeddings: you can build sentences of the form "the mouse escaped", "the mouse the cat chased escaped", "the mouse the cat the man owned chased escaped" that are grammatical and are arbitrarily long. These are similar to the language of matched parentheses "()", "(())" etc., and hence irregular for the same reasons.

However we can't conclude that English is irregular just from the fact that it has an irregular subset (for instance the language of all strings of parentheses does too, but that's clearly regular). The valid argument comes from the fact that all grammatical English strings of the form "(the [noun])*[verb]*" have matching numbers of nouns and verbs. The set of all strings of the form "(the [noun])*[verb]*" (call it $C$) is clearly regular, therefore if English were regular then the intersection of English and $C$ would be too. But the intersection is the irregular set of centre embeddings, hence English can't be regular.

One could argue that this argument isn't really correct: in practice the no-one ever uses centre embeddings with a depth of more than three, so the set of centre embeddings that actually exist is regular. This is a valid point, and is one of many reasons that the Chomsky hierarchy isn't always relevant to linguistics. But there are still a lot of situations where it is useful, for example saying that natural languages are context-free and then considering parsing them with pushdown automata suggests some possible models for how humans parse language.

$\endgroup$
  • $\begingroup$ I don't follow how C is regular. Maybe I am misunderstanding your definition? As I understand it, sentences of the form (the noun)* verb* with matching numbers of nouns and verbs is analogous to a^nb^n, well known not to be regular. $\endgroup$ – amalloy Oct 23 at 17:24
  • $\begingroup$ @amalloy Sorry, I phrased that wrongly originally (see the edit). I meant $C$ to refer to the set of all strings (including ones that are not grammatical like "the dog the cat the mouse escaped"). $\endgroup$ – rlms Oct 23 at 17:48
13
$\begingroup$

It doesn't really matter whether English (either words, or complete sentences) is a regular or say context free language or not. What matters is that it is very, very hard to produce a state engine or a grammar of a reasonable size whose language is reasonably close to the English language.

But let’s say we are told that English sentences are not allowed to have more than a billion letters. So it is a regular language. Does that knowledge gain us anything? No, it doesn’t.

$\endgroup$
  • 6
    $\begingroup$ I think this is the only real answer here. English is so nebulous that it is not a regular language for the trivial reason that it is not even a well-defined language. It is just like asking why mathematics is not a regular language. $\endgroup$ – user21820 Oct 23 at 7:28
  • $\begingroup$ Regular human communication that occurs over the spoken word is heavily context-dependent. $\endgroup$ – noɥʇʎԀʎzɐɹƆ Oct 23 at 19:54
  • 1
    $\begingroup$ @user21820 You should post that as an answer. It is the best answer here, and you've hidden it in a comment. $\endgroup$ – Ben I. Oct 23 at 20:06
  • $\begingroup$ @BenI.: Sorry about that; I didn't feel my short opinion-based comment was sufficiently well justified to be an answer. But since you say I should, I would. =) $\endgroup$ – user21820 Oct 24 at 2:19
8
$\begingroup$

(Making my comment into an answer as requested by Ben I.) English is so nebulous that it is not a regular language for the trivial reason that it is not even a well-defined language. It is just like asking why mathematics is not a regular language.

This may seem like a non-answer, and to some extent it is, because every question regarding English depends on the definition of "English", and it is undeniable that nobody can ever define "English" 100% precisely. Sure, if you choose to define English as some language that is generated by a context-free grammar, then of course you can prove things about it. For example, if English permits arbitrarily deep center embedding, then you might be able to use the pumping lemma to show that it is not regular, but necessarily the proof will depend on the exact definition of English.

In any case, it occurs to me that you may have a misunderstanding about the term "word". In normal (non-technical) usage, an English word is a string of letters (sometimes including hyphens too). In theoretical CS, "word" simply means a string of symbols. If we treat English as a set of grammatically valid sentences, then each English sentence is made up of English words, spaces and punctuation, but these words are not the same as the words of a formal grammar that generates English (even if there is one).

$\endgroup$
  • $\begingroup$ "In any case, it occurs to me that you may have a misunderstanding about the term "word"." – Just to give an example: given a formal grammar that generates English, the King James Bible would be "a word". Shakespeare's Romeo and Juliet would be "a word". This comment would be "a word". $\endgroup$ – Jörg W Mittag Oct 25 at 17:19
5
$\begingroup$

Using the terms as they are used in formal computer science, it is indeed true that any language with a finite longest word is regular. Here a language is a set of words over an alphabet, and a word over an alphabet is a sequence of symbols from the alphabet.

So if the language "English" is the set of words over a 26-symbol alphabet whose membership is determined by e.g. having a definition in the Oxford English Dictionary, then English is a regular language.

However, in the context in which the question arose the language "English" was probably intended to be the set of words over an alphabet which also includes space and punctuation marks, with membership determined by something like "being an utterance which a native speaker might make". Formalising that membership would be a challenge in itself. Is "Colourless green ideas sleep furiously." a word in English? What about "'Twas brillig."? But the odds are that it would require some notion of backreference to ensure correct correspondence of gender, plurality, or even name in the presence of anaphor or cataphor.

I note, as an aside, that I am given to understand that Swiss German, considered at the level of the grammatical sentence, has a correspondence mechanism which makes it not even context-free.

$\endgroup$
  • $\begingroup$ I'm curious what the longest English word is, and how it was proved that no longer words exist. No dictionary lists all English words. $\endgroup$ – reinierpost Oct 23 at 16:20
  • $\begingroup$ "[A]ny language with a finite longest word" Words are finite by definition. Even $\{0,1\}^*$, which doesn't have any longest word, doesn't contain any infinite words. $\endgroup$ – David Richerby Oct 23 at 18:03
  • 1
    $\begingroup$ @reinierpost According to Wikipedia, the longest published English word has 1909 letters. The longest name known has almost 190,000 letters, though it is disputed whether or not it counts as a "word." en.wikipedia.org/wiki/Longest_word_in_English. $\endgroup$ – alephzero Oct 23 at 19:46
  • $\begingroup$ @reinierpost how does one determine if a given word is or is not a bona fide English word (other than by looking in dictionaries?) $\endgroup$ – Jeremy Friesner Oct 23 at 23:25
  • $\begingroup$ @Jeremy Friesner: see if it's used in a sentence in a way that conforms with the rules of the English language. A dictionary is a good source, but it's not exhaustive. Words can be borrowed from other languages or can be built out of other words or phrases with the word formation rules of English. E.g. urbandictionary.com/define.php?term=lolled $\endgroup$ – reinierpost Nov 14 at 11:01
3
$\begingroup$

English is not a regular language not because it's irregular, but because it's not a language.

(In the formal sense, that is.)

The common claim from CS/formal-logic folks thae English (or any other human language) is not regular is based on nestability of grammatical constructs. Same idea as "language of balanced-parentheses strings is not regular", clearly provable by the pumping lemma. The problem here is that arbitrarily-nested grammatical constructs are not members of the language, because beyond some (indefinite but clearly existant) limit they're no longer intelligible.

Rather, English (and other human languages) aren't regular languages because they're not languages. There is no rigorous definition of what is or is not a member of the language. For some strings of words, most users of the language are in agreement as to whether or not they're in the language, but for plenty of others, nobody agrees, and for many, even most individuals are not sure.

$\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.