Author |
Topic: Binary tree pattern (Read 402 times) |
|
Mike_V
Junior Member
Gender: 
Posts: 60
|
 |
Binary tree pattern
« on: Oct 19th, 2003, 12:52am » |
 Quote  Modify
|
So a recursive pattern for an even pallindromic binary number is: S = 00 || 11 || 1S1 || 0S0
Find such a pattern for a left read full random binary tree. That is, you have a tree such that for every node there are two children: 0 and 1, and the number/length of branches is random, and the number is made by reading down the left side (and only advancing when you hit a branch with no node at 0).
A few examples, I'm not sure how common this terminology is:
/\ = 0 1
/\
/\ = 0 0 1 1
/\ = 0 1 0 1
/\
/\
/\ /\ = 0 0 1 1 0 1
/ \
/ \ / \
/\ /\ /\ /\ = 0 0 0 1 1 0 1 1 0 0 0 1 1 1 0 1
/\
modified to fix the tree for the 5th example
|
| « Last Edit: Oct 19th, 2003, 2:31am by Mike_V » |
 IP Logged |
Don't specify the unspecified.
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Binary tree pattern
« Reply #1 on: Oct 19th, 2003, 1:15am » |
Quote Modify
|
If I understand you correctly, each node wil contribure 01. If the node has children, more "01"'s may appear either after the 0 or after the 1. The same is true also for the children.
In that case, the recursive pattern may be:S= 01 || 0S1 || 01S.
|
|
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
Mike_V
Junior Member
Gender:
Posts: 60
|
|
Re: Binary tree pattern
« Reply #2 on: Oct 19th, 2003, 2:28am » |
Quote Modify
|
You do understand correctly.
But I believe that you'll see that your solution doesn't work on the 5th example I provided.
|
|
IP Logged |
Don't specify the unspecified.
|
|
|
BNC
Uberpuzzler
Gender:
Posts: 1732
|
|
Re: Binary tree pattern
« Reply #3 on: Oct 19th, 2003, 5:55am » |
Quote Modify
|
Yes, you're right.
I'm not familiar with "recursive patterns", so I'm not sure if it's premitted. But if it is, the following should solve the problem:
::S = 01 || 0S1 || 01S || 0S'1S'' , where S' and S'' are two other instances of S::
|
| « Last Edit: Oct 19th, 2003, 5:56am by BNC » |
IP Logged |
How about supercalifragilisticexpialidociouspuzzler [Towr, 2007]
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Binary tree pattern
« Reply #4 on: Oct 19th, 2003, 6:24am » |
Quote Modify
|
BNC hi,
For general knowledge (and if you want to read about it), this form of defining a family of instances is (also) called Context Free Grammars (or CFG) --> e.g. if we write S = 1S0 then we mean the family of grammers that are from the form {1n0n| n [in] [smiley=bbn.gif]}.
I think there is a problem with your solution since the pattern of S' and S'' is undefined.
For my opinion, the correct solution should be:
 S = SS || 0S1 || [emptyset]
p.s. - [emptyset] stands for null characters.
|
| « Last Edit: Oct 19th, 2003, 6:27am by Dudidu » |
IP Logged |
|
|
|
Mike_V
Junior Member
Gender:
Posts: 60
|
|
Re: Binary tree pattern
« Reply #5 on: Oct 19th, 2003, 11:51am » |
Quote Modify
|
BNC, you don't need the primes. It's acceptable to have two distinct instances of S. And if you ignore the primes, that was the answer that I had been thinking of.
Although, if we're allowing null characters, you can simplify it down a bit.
And yeah, I'm not so sure, but I believe Dudidu's answer also works.
|
|
IP Logged |
Don't specify the unspecified.
|
|
|
Dudidu
Full Member
Posts: 227
|
|
Re: Binary tree pattern
« Reply #6 on: Oct 20th, 2003, 1:18am » |
Quote Modify
|
on Oct 19th, 2003, 11:51am, Mike_V wrote:| ...And yeah, I'm not so sure, but I believe Dudidu's answer also works. |
|
Mike_V Hi,
The idea behind my solution works like this:
Starting from the root, every time we're in a vertex that has branches we use the S->0S1 step and then
the S->SS step, reaching a 0SS1 grammer. Now, we just continue recursivaly on the left child (using the "first" S in the grammer) and on the right child (...). If we reach a leaf node then we just use the S->[emptyset] rule to "terminate" this grammer branch.
Hopes that this help to understand the idea behind my solution  .
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print