automataformal-languagescomputability

Understanding Σ* and Σ in formal languages

If I have Σ={a} , what words does Σ* has ?

Σ*= {a,aa,aaa,aaaa.....} ?

Thanks

Solution

  • If your alphabet is Σ={a} then Σ*= {#, a,aa,aaa,aaaa.....} means all the possible n* a, including the empty string # (phi). Another way to produce that sequence is using grammars:

    S -> S
S -> aS
S -> #

    where # is the empty string.