Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hello I´m new to formal language and searching the solution for the following task:

Language: $L = \{0^{2i+1}|i\in\mathbb{N}_0\}$

Alphabet: $\Sigma = \{0\}$

I'm searching the resultion (sic) for: $\Sigma^+\setminus L$.

share|cite|improve this question
What do you mean by "resolution"? – Raphael Apr 11 '11 at 15:15

It seems like you're not certain on the terminology, so I'll try to explain the notation further.

The possible characters in the alphabet ($\Sigma$) is just zero. By definition, $\Sigma^+$ is all possible strings of alphabet characters with length greater than zero. So elements of $\Sigma^+$ are $\{0,00,000,\ldots\}$.

Now, in formal languages, $a^b$ means $\underbrace{a\ldots a}_{b \text{ times}}$. So $L$ consists of all strings that look like $\underbrace{0\ldots 0}_{2i+1 \text{ times}}$ for $i \in \mathbb{N}_0$.

From here, try writing out what strings in $L$ look like in the same way that I wrote out strings in $\Sigma^+$. Then to find $\Sigma^+ \setminus L$, look at what strings are in $\Sigma^+$ but are not in $L$.

share|cite|improve this answer

Hint 1: Write out some words in $\Sigma^+ \setminus L$ and try to find a pattern.

Hint 2: Write out the condition that a word be in $L$. Then negate it.

share|cite|improve this answer
Thanks for your comment. I´m a little bit confused because there is a 0 in the exercise. – LaPhi Apr 11 '11 at 7:39
Did you notice that 0 is the only character? – Yuval Filmus Apr 11 '11 at 13:31

This task (question) is a little bit prickly:

0$^{2i+1}$ means every odd natural number. So, the language is made up of 0$^1$ and 0$^3$ and 0$^5$... to infinite. However, zero exponentiate with a natural number is always zero.

ok, but our alphabet $\Sigma$ has only one entry, the zero. And the alphabet $\Sigma^+$ \ L (\ means without) is our alphabet without zero (-> 0$^{2i+1}$ = 0, ever), so it's empty, because $\Sigma$ has only 0.

That's what I would give to an answer, but I'm not sure. Might be it's right, may be it's rubbish

share|cite|improve this answer
$0^k = \underbrace{0 \dots 0}_k$ – Raphael Apr 11 '11 at 15:13
Echoing Raphael, $0^1$ means the string $0$, $0^3$ means the string $000$, and $0^5$ means the string $00000$. The bases (zero) stand for characters in your alphabet, so you're not supposed to treat them like numbers. You do treat the exponents like (natural) numbers, however. – Michael Chen Apr 12 '11 at 14:38
Thank you for you help. So it makes sense (to me). ;) $0^1$ $0^3$ $0^5$ is possible, because of 0$^{2i+1}$ However, $0^1$ is not allowed -> $\Sigma$ \ L -> {0}. Solution is: $\Sigma^+$ \ L : {000}, {00000}, {0000000} , ... >>The bases (zero) stand for characters in your alphabet, so you're not supposed to treat them like numbers. You do treat the exponents like (natural) numbers, however.<< This was the fact I didn't know... – jensen Apr 13 '11 at 9:30
The notation $L = \{0^{2i+1}|i\in\mathbb{N}_0\}$ stands for "the language $L$ consists of all strings of the form $0^{2i+1}$, where $i$ is an integer ($\mathbb{N}_0$ means zero is included)". My question to you: what happens when $i = 0$? Also, you seem to have it turned around: the strings you say are in $\Sigma^+ \setminus L$ are in fact in $L$. – Michael Chen Apr 13 '11 at 15:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.