A Recursively Defined Set of Strings

Question

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.

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

Answer 2

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