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.
$\begingroup$
$\endgroup$
7
-
45$\begingroup$ Because "English is really three languages stacked up wearing a trenchcoat" ? $\endgroup$– CriggieCommented Oct 23, 2019 at 3:22
-
6$\begingroup$ Are other human languages regular? I mean, is there a reason you picked out English other than we're using it here? $\endgroup$– user3445853Commented Oct 23, 2019 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$– reinierpostCommented Oct 23, 2019 at 16:16
-
2$\begingroup$ @Criggie: Three? More like several dozen and counting. $\endgroup$– VikkiCommented Oct 23, 2019 at 22:45
-
2$\begingroup$ @reinierpost At least that one is regular! $\endgroup$– user20574Commented Oct 24, 2019 at 8:41
|
Show 2 more comments
8 Answers
$\begingroup$
$\endgroup$
19
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.
answered Oct 22, 2019 at 11:36
-
42$\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$– rlmsCommented Oct 22, 2019 at 20:04
-
12$\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$– rlmsCommented Oct 22, 2019 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$ Commented Oct 23, 2019 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$ Commented Oct 23, 2019 at 8:35
-
3$\begingroup$ Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo $\endgroup$ Commented Oct 23, 2019 at 14:17
$\begingroup$
$\endgroup$
3
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.
-
$\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 toa^nb^n, well known not to be regular. $\endgroup$– amalloyCommented Oct 23, 2019 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$– rlmsCommented Oct 23, 2019 at 17:48
-
$\begingroup$ Do I understand correctly that e.g. English isn't regular because o/wise we would have too many rules of the kind
ab, a{2}b{2}, a{3}b{3}...? If so, the argument is ridiculous, as the maximum attested depth of centre-embedding in any language is 3 $\endgroup$– jaamCommented Sep 26, 2021 at 21:31
$\begingroup$
$\endgroup$
4
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.
-
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$ Commented Oct 23, 2019 at 7:28
-
$\begingroup$ Regular human communication that occurs over the spoken word is heavily context-dependent. $\endgroup$ Commented Oct 23, 2019 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.Commented Oct 23, 2019 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$ Commented Oct 24, 2019 at 2:19
$\begingroup$
$\endgroup$
5
(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).
-
$\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$ Commented Oct 25, 2019 at 17:19
-
$\begingroup$ This answer may be correct, but it is not what linguists mean when they say English is not a regular language - what they mean is rims's answer. $\endgroup$ Commented Aug 10, 2020 at 11:49
-
$\begingroup$ @reinierpost: My post did mention the issue of center embedding, and how one has to first decide what English is before the question of whether it is regular or not is even meaningful, because what some people consider English is not what the vast majority considers English... $\endgroup$ Commented Aug 10, 2020 at 16:22
-
$\begingroup$ @user21820 No doubt ... and Chomsky's approach (of defining that problem away) is common in mathematics and science, but not necessarily acceptable to a linguist. $\endgroup$ Commented Aug 11, 2020 at 19:58
-
$\begingroup$ @reinierpost: Yes indeed. In fact, in my personal opinion, English is a language that can be generated by a push-down automaton with a fixed number of (small) fixed-size stacks. The total stack size is bounded by the working memory size. That's neither a TM nor a CFG, but arguably shouldn't be simply considered an FSM either, even though it is equivalent to one. Same as a modern computer shouldn't be considered as an FSM, but rather a RAM with a large but limited memory. $\endgroup$ Commented Aug 12, 2020 at 12:58
$\begingroup$
$\endgroup$
6
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.
-
$\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$ Commented Oct 23, 2019 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$ Commented Oct 23, 2019 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$ Commented Oct 23, 2019 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$ Commented Oct 23, 2019 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$ Commented Nov 14, 2019 at 11:01
$\begingroup$
$\endgroup$
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.
answered Oct 24, 2019 at 17:04
$\begingroup$
$\endgroup$
English, at the word level (no sentences, let alone grammar, punctuation or paragraphs), is regular provided we assume there are a finite number of words (no matter whether there are 1 million, 2 million, 10 million or even more, as long as it is finite). If nothing else, this is due to the fact that all finite languages are regular. It is fairly easy to construct an NFA with a start state and epsilon transition to the start state of every word. Each of these states would then have a single character to move it to a next state, and any other moves to a dead state. Of course this isn't the best possible construction, and there are ways to group together common suffixes with epsilon transitions from valid prefixes (eg. skiing is valid, kayaking is valid, doging is not), but that is all irrelevant. Also, it is possible to write a regular expression for English words. Simply union together all the words- eg. airplane + avocado + ... + ball + ... + zebra + ... It would be a hell of a long expression, but is valid nonetheless.
English at the sentence level (never mind syntax, punctuation, sentence order etc.) is not regular, and this is easy to show using the pumping lemma. Consider some story, novel, article etc. that is larger than the number of states in our supposed DFA. Even if there are a billion states, surely we can find some English text with more characters than that. Now, we must be able to find some subsection that can be repeated twice, thrice ... infinitely many times and the piece still remains in valid English. It is nearly impossible to find this (even if y is a space, two spaces are considered a typo). Of course there are obscure examples that are debatable (eg. The tree grew bigger and bigger, The tree grew bigger and bigger and bigger ... ). It is debatable here how many times repeating "and bigger" would be acceptable. Even if the answer is infinite, it still does not mean English is regular.
The pumping lemma doesn't say there merely exists some w longer than p that can be split into xyz, it says that EVERY single w longer than p must satisfy this condition. Surely I can find another piece written in valid English that is long enough, but does not contain any of the obscure debatable examples (like "and bigger"). Applying the pumping lemma here clearly shows English is not regular.
$\begingroup$
$\endgroup$
1
Interesting conversation.
I think that the grammar of English is not regular, because the grammar was defined as programming language are defined.
But natural spoken English (or any other language) is regular.
The example that breaks regularity is {a^n b^n | n >= 0}, but I think that no human being is able to speak so well English that he/she can say a phrase similar to a^1000000 and b^1000000, and there does not exist any human being that can say if the person that say that it was correct of not.
So, I think that the regular language L = {a^nb^n | n<1000000} union a^1000000 a* b^1000000 b^*, is a regular language that will cover any real English conversation in this context.
So, grammatical English is not regular. But natural spoken English is regular.
IMHO
-
$\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ Commented Mar 28 at 9:00