[Solved]: Is a single symbol, not in a set, a language?

Problem Detail: 

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.

Asked By : Pampero

Answered By : Ran G.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3537

3.2K people like this

 Download Related Notes/Documents