I was reading about Turing machines and realized I'm not sure about the difference between the following scenario. Given the alphabet $\Sigma = \{a, b \}$, we have the following assertions:

  1. $a \in R $
  2. $\{a\} \in R$

I think that assertion $1$ is incorrect because $a$ is just a symbol, not a language. On the other hand $\{a\}$ is the language which contains only the $a$ symbol. Given that information, we can prove that $\{a\} \in R$ by trivially building a TM. Here, $R$ denotes the set of recursive languages.

Is my reasoning wrong? Thanks in advance.

  • 6
    $\begingroup$ If you repost this somewhere else, it would be useful to explain what the variable R stands for. $\endgroup$ – Robin Kothari Sep 14 '12 at 15:07
  • $\begingroup$ Well, hold on. If $R$ is taken to denote the set of regular languages, then $a$ may be interpreted as a regular expression for the language $\{a\}$, in which case it is true that $a \in R$. So you might see $a \in R$ somewhere, without it being wrong... $\endgroup$ – Patrick87 Sep 14 '12 at 17:22
  • $\begingroup$ @RobinKothari Thanks for your comment, I've made a clarification of what $R$ stands for. Anyway, I do not understand why this questions wasn't suitable for cstheory. $\endgroup$ – Pampero Sep 14 '12 at 21:47
  • $\begingroup$ @Patrick87: A regular expression and the language it represents are two clearly distinct objects. $\endgroup$ – frafl May 24 '13 at 16:43
  • $\begingroup$ @frafl Yes, but I'm not talking about that; I'm talking about how the notations aren't necessarily always clear and must be understood in context. Depending on the context, $a$ may mean the symbol, the regular expression, or the language of the regular expression. $\endgroup$ – Patrick87 May 28 '13 at 16:28

By the standard definitions, a language is always a set of (finite-length) words. This means that "$a$" is not a language, but either a symbol or a word.

If $R$ denotes all the regular languages (or alternatively, all the recursive languages), then indeed $a \notin R$. On the other hand, $\{a\}$ is a language, which is also regular (and recursive).

To complete the standard definitions:

  1. an alphabet is a finite set of symbols
  2. a word is a finite-length string of symbols
  3. a language is a set of words (and can be finite or infinite)

of course, there are many possible extensions to the above definitions, such as infinite-alphabet, infinite-length words, etc.

  • $\begingroup$ Thanks for your answer, that's exactly what I was looking for. $\endgroup$ – Pampero Sep 14 '12 at 21:43
  • 3
    $\begingroup$ Hey, not so fast. Sets can be nested! Even if the alphabet $\Sigma$ is a set containing two regular languages $a$ and $b$, the set $\{a\}$ is a finite-and-therefore-regular language over $\Sigma$. $\endgroup$ – JeffE Sep 14 '12 at 23:12
  • 1
    $\begingroup$ Part of the problem is that $a$ is not a language, but $a$ is a regular expression which represents the language $\{a\}$, so often $a$ will be used as shorthand for $\{a\}$. So in a sense, $a$ is not a language but $L(a)$ is. $\endgroup$ – jmite May 24 '13 at 16:41
  • $\begingroup$ It is unfortunate that there is no formal notational difference between a symbol in the alphabet, a string of length one, and a regular expression encoding a language whose only element has length one. $\endgroup$ – JeffE May 25 '13 at 14:13

I guess this is not what you were looking for, but I'd like to answer this from the viewpoint of pure set theory:

  1. Let $\Sigma$ be any finite set, we call its elements symbols and $\Sigma$ an alphabet.
  2. A word over $\Sigma$ is a tuple of elements from $\Sigma$. Tuples can be defined using set theory in a lot of different ways (some of them can be found in WP:Tuples). Especially for the $1$-tuple, there are at least three definitions. Let $(a)$ be the tuple that contains only the set $a$. Then one can define e.g.
    • $(a):=a$,
    • $(a):=\{\{a\},\{\{\{\emptyset\},a\}\}\}=\{(1,a)\}$ (tuple as finite function) or
    • $(a):=\{a,\{\emptyset,a\}\}=(\emptyset,a)$ (nested ordered pairs).
  3. A language over $\Sigma$ is a set of words, i.e. a set of tuples whose elements are in $\Sigma$.

If we assume that tuples (and thus words) are finite, then languages are always countable. Whether a symbol $a \in \Sigma$ is also a language (over $\Sigma$ or any other alphabet) now depends on your definition of tuples:

  1. If $(a)=a$ then any finite set $S$ can be seen as a language over $S$, containing all words of length $1$. So if $a\in \Sigma$ is a finite set (remember all "objects" in set theory are sets), then it is a language.
  2. If not only $a \in \Sigma$, but $a \subset \Sigma$ (e.g. WP:Peano arithmetic), then $a$ is even a language over $\Sigma$ if we define $(a):=a$ and similar cases are possible for the other definitions of tuples, if $\{(a)\} \in \Sigma$.

Conclusion: if you like to ensure that $a \in \Sigma$ is not a language, make your symbols uncountable, e.g. let $\Sigma=\{[i-1,i]\mid i\in {1,\dots,k}\}$, where $[a,b]$ means the closed real interval.


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.