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
0 comments:
Post a Comment
Let us know your responses and feedback