0
$\begingroup$

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

$\endgroup$
2

3 Answers 3

4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks for your comment. I´m a little bit confused because there is a 0 in the exercise. $\endgroup$
    – LaPhi
    Apr 11, 2011 at 7:39
  • $\begingroup$ Did you notice that 0 is the only character? $\endgroup$ Apr 11, 2011 at 13:31
0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ $0^k = \underbrace{0 \dots 0}_k$ $\endgroup$
    – Raphael
    Apr 11, 2011 at 15:13
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 12, 2011 at 14:38
  • $\begingroup$ 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... $\endgroup$
    – jensen
    Apr 13, 2011 at 9:30
  • $\begingroup$ 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$. $\endgroup$ Apr 13, 2011 at 15:07

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.