2
$\begingroup$

Given a language $L \subseteq \Sigma^*$, (it could be Italian, English, C++ or anything else), should we consider the punctuation (".", ";", "->") as a part of the alphabet $\Sigma$ upon the language is built on or not?

$\endgroup$
3
$\begingroup$

Yes, for a couple of reasons.

  • In natural language, punctuation changes the parsing and meaning of sentences. The classic example is "The panda eats shoots and leaves" (describing its diet) has a different meaning than "The panda eats, shoots, and leaves" (describing its violence before it departs). A parser should, in theory, generate different parse trees for these two sentences.

  • In formal languages, punctuation doesn't really exist as an entity separate from other symbols. So unless adding and removing punctuation from a word NEVER changes its membership in a language, you want to consider it, since any decision procedures will need to know about this.

For formal languages, we can't ignore that sometimes, what you call punctuation, might change the properties of the language.

For instance, it's easy to accept the set $\{ w.w^R \mid w \in \Sigma^* \}$ with a deterministic pushdown automaton. But remove the $.$ character as a delimiter, and we need non-determinism to guess where the end of the first string is, and where its reversal starts.

$\endgroup$
3
$\begingroup$

Yes. The alphabet is the set of all characters that can appear in the strings you're interested in, since a string is defined to be a sequence of characters from the alphabet. If you state that punctuation is not in the alphabet, then "Hi, Gerardo!" is not a string.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy