On page 103 of Mike Sisper's Introdution to Theory of Computation, it says that the grammar has 27 terminals (26 being the letters of the English Alphabet and 1 being the space character) but in the rules above, I don't see those 27 terminals. I only see 10 which are "a", "the", "boy", "girl", "flower", "touches", "likes", "sees", and "with". book excerpt So my question is, what does the book mean? Is this an error?

  • 1
    $\begingroup$ They counted every letter a-z plus a space character. It is explaind in parentheses right after the "27 terminals", so the word "with" for instance consist is a word of 4 terminals w, i, t, h. $\endgroup$
    – ttnick
    Apr 8, 2023 at 20:17
  • $\begingroup$ @ttnick How does one determine what terminals a CFG has from looking at its rules? $\endgroup$
    – Sbavert
    Apr 9, 2023 at 5:38
  • $\begingroup$ @ttnick "In parentheses" is one claim. The rule list shows ten non-variables, giving rise to Sbeve's question. I'd call it an inconsistency, or lack of completeness if those ten are neither variables nor terminals. $\endgroup$
    – greybeard
    Apr 9, 2023 at 6:45

1 Answer 1


The author defines terminals in the following way.

The string consists of variables and other symbols called terminals.

When you are writing grammar for a human language, it is better to treat letters as symbols rather than words (sequence of letters) which although correct tend to be in thousands. One concern remains which is generation of new nouns. How would generate X Æ A-12 in the latter case, unless you are constantly updating the massive corpus, that you call the alphabet?

$G_2$ is however just a toy example spanning a small fragment of the English language, in which case $\Sigma_1$ = {a, the, boy, girl, flower, touches, likes, sees, with, ␣} would be as fine as $\Sigma_2$ = {a, b, $\ldots$ , z, ␣} if not more.

  • $\begingroup$ "How would generate X Æ A-12 in the latter case, unless you are constantly updating the massive corpus, that you call the alphabet?" I don't understand why I would need that. It is just a toy example so it could just be a language with a limited number of words allowed. Also, the example strings of the language only contain words from the 10 words I listed in the question. It adds to the confusion because it implies that no other strings are possible for this language. $\endgroup$
    – Sbavert
    Apr 9, 2023 at 11:38
  • $\begingroup$ @Sbeve When you are teaching a concept, it is best to keep it as broad as possible, which is why the author choose to mention 27 as the number of terminals, and not just 10. Michael Sipser's lectures on Theory of Computation are available on YouTube, maybe you can refer to that. $\endgroup$
    – ihsingh2
    Apr 9, 2023 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.