A community for students. Sign up today!
Here's the question you clicked on:
 0 viewing
 2 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.
 2 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

shandelman
 2 years ago
Best ResponseYou've already chosen the best response.0It'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.
Ask your own question
Ask a QuestionFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.