Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Have I done this right? I have shown that every element of Σ exists in Σ*, so is it ok to do what I did in step 5?

 If Σ = {s,i, n, g}, show that singing is in Σ*.
 Solution: (in 5 steps)
    1) Since λ ∊ Σ* and i ∊ Σ, i ∊ Σ*. 
    2) Since i ∊ Σ* and n ∊ Σ, in ∊ Σ*.
    3) Since in ∊ Σ* and g ∊ Σ, ing ∊ Σ*.
    4) Since ing ∊ Σ* and s ∊ Σ, sing ∊ Σ*. 
    5) Since sing ∊ Σ*, and ing ∊ Σ*, singing ∊ Σ*.
share|cite|improve this question

This can't be optimal. Either your definition of the Kleene star permits arbitrary concatenation, in which case you can do everything in one step, or it doesn't, in which case you need seven steps. Your step 5 is essentially using the theorem that $\Sigma^\star=\Sigma^\star \Sigma^\star$.

share|cite|improve this answer
Hi Vadim. I wish I knew what you were even talking about. The instructor said it can be done in 5 steps. He hasn't been very effective in explaining things and only spent 20 minutes on this very topic. He said prove ing is in E* and then you can add S to id.. that's all I know. – Hermes Trismegistus Jun 16 '13 at 23:52
Well, if you have the theorem I mention, then you can do it in five steps as you have it. Or, you could generalize that theorem as below, and do it in one step: $\Sigma^\star=\Sigma^\star\Sigma^\star\Sigma^\star\Sigma^\star\Sigma^\star\Sigma‌​^\star\Sigma^\star\supseteq \Sigma\Sigma\Sigma\Sigma\Sigma\Sigma\Sigma\ni singing$ – vadim123 Jun 16 '13 at 23:54
@vadim123 One could argue that the 'generalization' of the theorem from $\Sigma^*=\Sigma^*\Sigma^*$ to arbitrary concatenations also takes some steps... – Steven Stadnicki Jun 16 '13 at 23:56
Thanks guys. I wish my instructor was as effective, it's really hard to learn this stuff from scratch and there is only one session per week where he tries to squeeze in 200 slides into 3 hours which always leads to him rushing. – Hermes Trismegistus Jun 16 '13 at 23:59

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.