1
$\begingroup$

This problem has confused me a lot, can any of you help me out. Thank you.

$\endgroup$
  • 2
    $\begingroup$ (1) Every problem has a unary encoding. (2) A unary language is a subset of $\sigma^*$ for some letter $\sigma$. No more no less. $\endgroup$ – Yuval Filmus Oct 16 at 21:29
1
$\begingroup$

A unary language is a subset of $\sigma^*$ for some letter $\sigma$. If your language is of this form, then it is unary. Otherwise it isn't.

A unary encoding is an encoding of some data as a subset of $\sigma^*$. For example, one possible unary encoding of the natural numbers is $n \mapsto 1^n$. Any language in which instances are unary encoded is a unary language, simply because it is a subset of $\sigma^*$. For example, the language of all primes encoded in unary is a unary language.

$\endgroup$
  • $\begingroup$ Thank you for your time sir $\endgroup$ – KKP Nov 5 at 21:12
  • $\begingroup$ Can you also provide me a reference for your answer. $\endgroup$ – KKP Nov 5 at 21:13
  • $\begingroup$ I'm not quite sure what you mean by reference. $\endgroup$ – Yuval Filmus Nov 5 at 21: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.