While reading the book theory of computation by Michael Sipser, I did not understand the language given below. I will explain the problem first

$$L = \{1^n :n \in \mathbb{Z}\}$$

Where $\mathbb{Z}$ is a set of integers.

Question :I am not able to understand the string that belong to the given set will look like.

I know if input alphabet is $\{0,1\}^*$ then string 0101 (5 in decimal).


Forget about strings meaning anything. For any symbol $a$ and natural number $n$, $a^n$ is the string made from $n$ copies of $a$. So $a^1=a$, $a^2=aa$, $a^5=aaaaa$ and $a^0$ is the empty string, usually written as $\varepsilon$ or $\lambda$.

The set $\{1^n\mid n\in\mathbb{Z}\}$ isn't well-defined (did Sipser really write that?), since $-1\in\mathbb{Z}$ but $1^{-1}$ doesn't make sense: what would $-1$ copies of the symbol $1$ look like?

However, the set $\{1^n\mid n\in\mathbb{N}\}$ is just $\{1^0, 1^1, 1^2, 1^3, \dots\}$, i.e., $\{\varepsilon, 1, 11, 111, \dots\}$ (I'm considering zero to be a natural number; delete $\varepsilon$ if you think that one is the first natural number). Now, strings such as $111$ can be interpreted as numbers written out in some base (unary, binary, decimal, whatever). But the definition is just giving you a set of strings.


I think you need to understand the unary encoding. The set $$L =\{1^n:n \in \mathbb{Z}\}$$

contain strings like 1,11,111,1111 so on . Where 1,11,111,1111 represent 1,2,3,4 respectively in unary encoding.


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.