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.

Hey! We 've verified this expert answer for you, click below to unlock the details :)

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

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.

Looking for something else?

Not the answer you are looking for? Search for more explanations.