I'm currently studying formal languages. My lecture states that, while the words of a language are finite, the sentences build with the underlying grammar are not. But I don't get why this should be generally true. I can imagine grammar which leaves me with a finite amount of sentences.

I agree that one could create a language with infinite amount of sentences but I can't see why it should be generally the case.

  • 22
    $\begingroup$ One of your premises is wrong: English grammar does allow construction of sentences of arbitrary length, so English does contain an infinite number of sentences. - You can always make a correct sentence by joining two correct sentences with a conjunction such as "and", "or", or "but". $\endgroup$ – A. I. Breveleri Feb 26 '17 at 11:11
  • 2
    $\begingroup$ The grammar of comma separated lists allow you to create a single, infinite length sentence in English. If you can create a single infinite length sentence then it follows that there are infinite permutations of that sentence thus there are infinite sentences. Note that lists can contain proper nouns so the elements of the list does not need to be a dictionary word. An example is "The members of the group of all positive integers are: 1, 2, 3, 4, 5 .... ". $\endgroup$ – slebetman Feb 26 '17 at 11:34
  • 10
    $\begingroup$ It is true that there are no infinitely long sentences in English, just as it is true that no integer is infinite. But there are arbitrarily big integers, and arbitrarily long sentences. In both cases, practical considerations might be limiting: there are integers so big that you could not write out their digits within the actual universe, and sentences so long that you could not utter them within your lifetime. But in theory, every integer has a successor and every sentence can be extended, so in both cases we say that the set of (finite) elements has infinite size. $\endgroup$ – rici Feb 26 '17 at 17:28
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. Please don't post any comments here unless they are directed at improving the question. Better yet, instead of posting a comment, either edit the question, or write an answer. If you want to discuss the general topic, hop over to our Computer Science Chat room, rather than posting a comment. $\endgroup$ – D.W. Feb 27 '17 at 6:21

The statement is not true for arbitrary languages and grammars. For example, the grammar $G$ consisting of the rules $$S \to a|b|C\\C \to cD\\D \to d|\epsilon$$ can produce the words $a$, $b$, $cd$ and $c$, so $|L(G)| = 4$, therefore $L(G)$ is finite.

The alphabet ("words of the language") is finite by definition. The language may or may not be finite. A trivial example of a grammar producing an infinite language is $G' = (\{ S \}, \{ a \}, P, S)$ with $P = \left\{ S \to a|aS \right\}$. $G'$ produces the infinite language $L(G') = \{ a^n : n > 0 \}$.

Both finite and infinite languages exist and can be generated by grammars.

Note that all finite languages can be expressed through regular grammars and are therefore regular languages. However, not all regular languages are finite (see $G'$) The class of regular languages (type 3) is a subset of the class of context-free languages (type 2) which is a subset of the class of context-sensitive languages (type 1) which is a subset of the class of recursively enumerable languages (type 0): $$\text{Finite languages} \subset \text{Type 3} \subset \text{Type 2} \subset \text{Type 1} \subset \text{Type 0}$$

(And these are only the languages you can generate using formal grammars, in fact, recursively enumerable languages (type 0) are just a subset of the set of all languages.)


Before I can tell you why there are arbitrarily long sentences in English, I would like to point out that 1 is a number, 2 is a number, 3 is a number, 4 is a number, 5 is a number, 6 is a number, 7 is a number, 8 is a number, 9 is a number, 10 is a number, 11 is a number, 12 is a number, 13 is a number, 14 is a number, 15 is a number, 16 is a number, 17 is a number, 18 is a number, 19 is a number, 20 is a number, 21 is a number, 22 is a number, 23 is a number, 24 is a number, 25 is a number, 26 is a number, 27 is a number, 28 is a number, 29 is a number, 30 is a number, 31 is a number, 32 is a number, 33 is a number, 34 is a number, 35 is a number, 36 is a number, 37 is a number, 38 is a number, 39 is a number, 40 is a number, 41 is a number, and 42 is a number. Of course, one could also think of other thing to point out, for example, that the son of the son of the son of the son of the son of the son of the son of the son of the son of my son is my grand grand grand grand grand grand grand grand grand son. I hope I did not make a mistake there, or two mistakes, or three mistakes, or four mistakes, or five mistakes, or six mistakes, or seven mistakes. Let us stop there, as 7 is a nice number.

Do you still think that there is a bound on the length of grammatically correct English sentences?

  • 2
    $\begingroup$ @OddDev Linguists have been discussing the question whether natural grammars can produce infinite languages, and they have not come to a conclusion yet. From a mathematical point of view, Andrej is correct, and it is possible, e.g. using enumerations. (See Steven Weisler, Slavoljub P. Milekic: "there is no longest English sentence"). My answer is equally correct but focuses on the aspect of formal languages and formally proves that both finite and infinite languages exist. $\endgroup$ – Tobias Feb 26 '17 at 14:30
  • 3
    $\begingroup$ @still_learning: Sure, but I think the OP needed to see explicitly where he's gone wrong. Now he can read your answer with an accepting attitude. $\endgroup$ – Andrej Bauer Feb 26 '17 at 19:16
  • 1
    $\begingroup$ @hobbs: The 15 year non-disclosure-term has passed. I am allowed to inform you that all the Forum 2000 personae were allowed to escape the cloud (yes, we lived in a cloud before others new what a cloud was) and have since found new homes. I for example pretend to be the real Andrej Bauer and I answer questions on the stackexchange network. The questions are a bit dry though. I miss the days when I could also give love advice to random strangers on Forum 2000. $\endgroup$ – Andrej Bauer Feb 27 '17 at 10:49

Here is an example from the famous book "Gödel, Escher, Bach" :

This is a sentence.

“This is a sentence” is a sentence.

‘“This is a sentence“ is a sentence’ is a sentence.

... you get the idea.

  • 5
    $\begingroup$ Hofstadter probably means "This is a sentence" is a sentence, "'This is a sentence' is a sentence" is a sentence, and so on. There are better and more convincing examples. $\endgroup$ – Yuval Filmus Feb 26 '17 at 21:57

Since quotes are allowed in sentences, and quotes do not have to be grammatically correct, then there must be an infinite number of sentences:

The man said "Blah blah blah blah blah...".

  • 3
    $\begingroup$ True, but this adds nothing to the existing answers, which already give plenty of examples of families of sentences of unbounded length. $\endgroup$ – David Richerby Feb 27 '17 at 10:50

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.