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:
- $a in R $
- ${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:
- an alphabet is a finite set of symbols
- a word is a finite-length string of symbols
- 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
