470,848 Members | 1,232 Online

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!
Jul 17 '05 #1
1 1649 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
| 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!
Jul 17 '05 #2

### This discussion thread is closed

Replies have been disabled for this discussion.

### Similar topics

 2 posts views Thread by A. Wiebenga | last post: by 18 posts views Thread by free2cric | last post: by 15 posts views Thread by Anton Gavrilov | last post: by 23 posts views Thread by Jason | last post: by 5 posts views Thread by Franco, Gustavo | last post: by 1 post views Thread by David Van D | last post: by 1 post views Thread by PEB | last post: by reply views Thread by ryjfgjl | last post: by 1 post views Thread by DANILIN | last post: by reply views Thread by tracyyun | last post: by 1 post views Thread by MarkDoronin | last post: by reply views Thread by sjain6 | last post: by reply views Thread by jackhack | last post: by reply views Thread by shivajikobardan | last post: by reply views Thread by gglobus | last post: by reply views Thread by Ravipg | last post: by