Question

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.

First, my question is that how can A = A^2?

Answer 1

what is an alphabet?

Answer 2

oh i see and multiplication is given by concatenation. so i guess your alphabets have to be either empty or each string is infinitely long

Answer 3

Yes, well each string does not have to be infinitely long. It can be any length of string. Here's my response, please review it if you'd like:

False if $A = \emptyset$, but true otherwise. First, if $A = \emptyset$, then the premise is true, but the conclusion is false, since $\lambda \notin \emptyset$ and so $\lambda \notin A$. Therefore the claim is false for $A = \emptyset$. Second, if $A \neq \emptyset$, and if $A = \left\{\lambda\right\}$, then $A = A^2$ indeed and obviously, $\lambda \in A$. Thus the claim is true for this case. Lastly, for all other cases, the premise is always false, since $A$ can never be equal to $A^2$ unless $A = \emptyset$ or $A = \lambda$. Thus, the claim is vacuously true if and only if $A \neq \emptyset$.

Answer 4

Correction on last statement Thus, the claim is vacuously true for all other cases, and so the claim is true except when A = \[\emptyset\]