0

Describe the strings in the set $S$ of strings over the alphabet $\Sigma = \{a,b,c\}$ which are defined recursively by:

(1) $a$ is in $S$, and

(2) if $x$ is in $S$, then $ax$ is in S, $xb$ is in $S$ and $xc$ is in $S$.

So far I have in $S$:

a, aa, ab, ac, aaa, aab, aac, aab, abb, acb, aac, abc, acc, aaaa, aaab, aaac, aaab, aabb, aacb, aaac, aabc, aacc, aaab, aabb, aacb, aabb, abbb, acbb, aacb, abcb, accb, aaac, aabc, aacc, aabc, abbc, acbc, aacc, abcc, accc

My question really is whether or not I using the recursive definition correctly, since I can't seem to pick out a regular pattern. I'm confused because there are three definitions, $ax$, $xb$ and $xc$.

Any help is appreciated.

hardmath
  • 37,015
torikolpacoff
  • 47
  • What have you tried so far? (Questions on Math.SE get more attention when the poster includes what they have tried) – parsiad Jun 14 '16 at 22:55
  • 3
    Look at some examples of strings in $S$ -- you may notice a pattern... – David C. Ullrich Jun 14 '16 at 22:58
  • A recursive definition is much like a proof by induction. There is a base case (or cases), which in your problem is $a\in S$. Then there are the rules: if $x\in S$, then also $ax, xb, xc \in S$. These act like the induction step: assume $x\in S$ and conclude that these longer strings (longer by one character) must also belong to $S$. – hardmath Jun 15 '16 at 20:23

2 Answers2

1

Ok, I'll tell you the answer. A string is in $S$ if and only if it consists of $1$ or more $a$'s followed by $0$ or more $b$'s and $c$'s.

If you look at the strings you got that seems right, right? A formal proof will be by induction.

David C. Ullrich
  • 89,985
0

Hint: Start with $a\in S$, then you can append $a$ from left and $b,c$ from right, that's the rule.

The words that can arise this way will be in $S$.

Berci
  • 90,745
  • That's just a rephrasing of the definition. In particular it's a rule for generating the strings in $S$. I believe we want a non-recursive description - a string is in $S$ if and only if... – David C. Ullrich Jun 14 '16 at 23:03
  • Yes. Get a sheet of paper and a pen, and start generating yourself. That's the hint basically. You will get a clearer picture about $S$ then, and probably you could also find the non-recursive description. – Berci Jun 20 '16 at 22:06
  • Erm, thanks. I posted an answer including the explicit description several days ago... – David C. Ullrich Jun 20 '16 at 22:51