3
$\begingroup$

For example;

Is {0,1,{a,b,c},d,e} a valid alphabet to form a language over and is it usable in any context?

$\endgroup$
3
$\begingroup$

An alphabet is a set of symbols, therefore if your you treat $\{a,b,c\}$ as a single symbol (in some other alphabet), it is a valid alphabet.

$\endgroup$
  • $\begingroup$ Any example usage of this? $\endgroup$ – WeCanBeFriends Aug 3 at 16:13
  • 1
    $\begingroup$ @WeCanBeFriends Exactly like any other alphabet. $\{a,b,c\}$ is just another symbol, so it can be written on a single tape cell, but none of the $a, b$ or $c$ can be written individually, the same way you cannot write just a half of $0$ or any part of any other symbol. $\endgroup$ – Gogis Aug 3 at 16:17
  • $\begingroup$ @WeCanBeFriends But this only concerns the standard model of the Turing machine and there are many, many others. $\endgroup$ – Gogis Aug 3 at 16:18
  • $\begingroup$ What is the advantage to having {a.b,c} in the alphabet, as opposed to another symbol k? I'm not sure of a situation where it would be useful to have this set $\endgroup$ – WeCanBeFriends Aug 3 at 16:20
  • $\begingroup$ @WeCanBeFriends Random example from the top of my head: Imagine you would need to construct a TM that would be given a set of 3 numbers from the range $0-100$ and accept iff their average would be $> 47$. It would be more convenient to describe the TM using an alphabet where each input would be represented by a single symbol, because that way the TM would only need 2 states. $\endgroup$ – Gogis Aug 3 at 17:28

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.