470,848 Members | 1,232 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 470,848 developers. It's quick & easy.

Please help with this question

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
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!
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
By using this site, you agree to our Privacy Policy and Terms of Use.