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".
So my question is, what does the book mean? Is this an error?
$\begingroup$
$\endgroup$
3
-
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$– ttnickApr 8 at 20:17
-
$\begingroup$ @ttnick How does one determine what terminals a CFG has from looking at its rules? $\endgroup$– SbeveApr 9 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$– greybeardApr 9 at 6:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$– SbeveApr 9 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$– ihsingh2Apr 9 at 12:25