Got Homework?
Connect with other students for help. It's a free community.
Here's the question you clicked on:
 0 viewing
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.
 one year ago
 one year 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.
 one year ago
 one year ago

This Question is Closed

shandelmanBest ResponseYou've already chosen the best response.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.
 one year ago
See more questions >>>
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.