Question

Discrete Math: Formal Languages: Suppose that A is a subset of V*, where V is an alphabet. Prove that if A = A^2, then the empty string is in A.

Answer 1

It's been a while since my last formal languages class, so take all of this with a grain of salt.

Let's just get concrete for a second. I'm gonna use e for the empty string.

Let's say V = {0,1}. Then V* = {e,0,1,00,01,10,11,...}

So A is some subset of that infinite set. We also know that A = A^2. A^2 contains each element of A concatenated once to each other element of A.

At first, this seemed impossible to me. I mean, if A has 1 element, then shouldn't A^2 have two? How could they be equal? Then I realized that A could be infinitely long. So let's pretend that A is the subset that consists of only those terms with 0. That is, A = {0,00,000,0000,00000,...}. Now, let's assume that e is not a member of this set. Then A^2 would be {00,000,0000,00000,etc.} Notice this is not the same thing! It contains one fewer element than A did: the single 0.

What if we put the e back in there so that A = {e,0,00,000,...}? Well, now A^2 = {ee,e0,e00,e000,...} but ee is just e, and e0 is really just 0, and so on, so it really is the same language all over again.

What I've done isn't really a proof, but hopefully it serves as an explanation.