1

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 ∊ Σ*.
Hermes Trismegistus
  • 429

1 Answers1

0

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

vadim123
  • 82,796
  • 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