Quantcast

A community for students. Sign up today!

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

windsylph

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

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

    what is an alphabet?

  2. satellite73
    • 2 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
    • 2 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
    • 2 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

Ask a Question
Find 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
  • 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.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.