Please help with this question

[Jack Smith]

Can some one help me with this proof?

Let L be the language of strings over {a,b} recursively defined by the
following set of rules
(i) the string ^ is in L (^ is the null string).
(ii) for every x an element of L the strings bax, baax, bbax, and
bbaax are in L.
(iii) nothing is in L unless the first two rules require it.

Let T be the set of strings over {a,b} such that each string in T is
either empy or starts with b, ends with a, and contains no substring
of more than two repeated characters. Show the L = T.

The proof requires me to use Induction to prove that L is a subset (or
equal) to T. Then it requires me to use induction again to show T is
a subset (or equal) to L. By showing this the proof is complete. But
I need help on how to do the induction. Any help is appreciated.
Thanks!

[Elaine Jackson]

You want to show, by induction on n, that any string over {a,b} whose length
does not exceed n belongs to L iff it belongs to T. For n=0, it's obvious: the
empty string belongs to both languages. The procedure is to assume the
hypothesis holds for strings of length not exceeding some arbitrary n, and show
on that basis that it also holds for strings of length (n+1).

Notice that a string in L of length (n+1) is either
i) bax for some string x in L of length (n-1), or
ii) baax for some string x in L of length (n-2), or (...etc).

Notice that, if a string S over {a,b} satisfies the condition "contains no
substring of more than two repeated characters", then so does any substring of
S.

HTH

"Jack Smith" <st*******@yahoo.com> wrote in message
news:20**************************@posting.google.c om...
| Can some one help me with this proof?
|
| Let L be the language of strings over {a,b} recursively defined by the
| following set of rules
| (i) the string ^ is in L (^ is the null string).
| (ii) for every x an element of L the strings bax, baax, bbax, and
| bbaax are in L.
| (iii) nothing is in L unless the first two rules require it.
|
| Let T be the set of strings over {a,b} such that each string in T is
| either empy or starts with b, ends with a, and contains no substring
| of more than two repeated characters. Show the L = T.
|
| The proof requires me to use Induction to prove that L is a subset (or
| equal) to T. Then it requires me to use induction again to show T is
| a subset (or equal) to L. By showing this the proof is complete. But
| I need help on how to do the induction. Any help is appreciated.
| Thanks!