# Formal language problem

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$.

-
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$.

-

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.

-
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

-
$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