I have a question on the multiplication of sets of words as it is defined in Cohen's Intro To Computer Theory. He gives the definition: if S and T are sets of strings of letters, the product of the sets, ST = {All combinations of string from S concatenated with strings from T}.

The definition is easy enough to understand. But after giving a few standard examples, he gives an example along the lines of: S = {$\alpha $ a b}, T = {$\alpha $ a}

ST = {$\alpha $ a a aa b ab}

(I"ve used $\alpha$ to denote the empty string)

Basically, why is $\alpha \alpha$ = $\alpha$ in the product set and $\alpha$a = a ?


An empty string isn't zero, if you're looking at it and expecting αa=0 or αa={} then you're thinking about it like you would integers. Which if they were, you'd be correct. But you have to think about it in the form of strings, which is what you're dealing with.

Think of it like this,

α=' '

so 'a'+ ' ' ='a'

and ' '+' '=' '

  • $\begingroup$ Okay. It makes sense now. The last line in your answer really drives it home. So $\alpha+\alpha$ = ' ' + ' ' = ' ' = $\alpha$. Thanks. $\endgroup$ – Sadio Apr 20 '16 at 14:25

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.