0
$\begingroup$

Given the set:

$$\{x | x \in \{a, b\}*~\text{AND}~|x| = 4~\text{AND}~\exists y \in \{a,b\}* : (x = aya)\}$$

Why does the answer look like this: $\{aaaa, aaba, abaa, abba\}$? What I don't understand is why $bbbb$ isn't part of the answer? Does $a$ means $x$ and $y$ means $b$? Could someone just translate the given set in plain English? Thanks in advance!

$\endgroup$
2
  • $\begingroup$ @BrianO, but what does y mean? $\endgroup$
    – John
    Oct 29, 2015 at 4:00
  • $\begingroup$ I moved my comment to an answer, so if it's still not clear, then ask again below the answer. Thanks. $\endgroup$
    – BrianO
    Oct 29, 2015 at 4:03

1 Answer 1

Reset to default
1
$\begingroup$

Call the set $S$. It's defined by: $$ x \in S \iff \lvert x\rvert = 4 \:\&\: \exists y \in \{a,b\}^*\, x = aya $$ In plain English, a string over the alphabet $\{a,b\}$ is in $S$ if and only if

  • its length is 4, and
  • it begins and ends with $a$.

This leaves only the four possibilities $aa, ab, ba, bb$ for $y$, and any $x$ in $S$ will be $aya$ for one of those four possible $y$s.

$\endgroup$
3
  • $\begingroup$ Thanks for the reply! @BrianO. I'm confused about why there are only possibilities for y that are aa, ab, ba, bb when there is {a,b}*? $\endgroup$
    – John
    Oct 29, 2015 at 4:06
  • 1
    $\begingroup$ For $x$ in the set, $x$ has length 4 and begins and ends with $a$. So $x$ can be written $x = aya$ for some substring $y$ in the middle. So $y$ has to have length 2, and there are only 4 possibilities over the alphabet $\{a,b\}$. To really spell it out: $4 = |x| = |aya| = |a| + |y| + |a| = 1 + |y| + 1$. $\endgroup$
    – BrianO
    Oct 29, 2015 at 4:08
  • $\begingroup$ That sounds like an "aha!" -- good :) You're welcome. $\endgroup$
    – BrianO
    Oct 29, 2015 at 4:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .