Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

windsylph

  • 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. First, my question is that how can A = A^2?

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

    what is an alphabet?

  2. anonymous
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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

  3. windsylph
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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$.

  4. windsylph
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  5. 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