Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing


  • 3 years ago

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.

  • This Question is Closed
  1. shandelman
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

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

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy