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.

At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Get our expert's

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this and thousands of other questions.

A community for students.

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.

Computer Science
See more answers at brainly.com
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your free account and access expert answers to this and thousands of other questions

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.

Not the answer you are looking for?

Search for more explanations.

Ask your own question

Other answers:

Not the answer you are looking for?

Search for more explanations.

Ask your own question