wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Binary tree pattern
        
(Message started by: Mike_V on Oct 19^th, 2003, 12:52am)

Title: Binary tree pattern
Post by Mike_V on Oct 19^th, 2003, 12:52am

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

Title: Re: Binary tree pattern
Post by BNC on Oct 19^th, 2003, 1:15am

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:[hide]S= 01 || 0S1 || 01S[/hide].

Title: Re: Binary tree pattern
Post by Mike_V on Oct 19^th, 2003, 2:28am

You do understand correctly.

But I believe that you'll see that your solution doesn't work on the 5th example I provided.

Title: Re: Binary tree pattern
Post by BNC on Oct 19^th, 2003, 5:55am

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:
::[hide]S = 01 || 0S1 || 01S || 0S'1S'' , where S' and S'' are two other instances of S[/hide]::

Title: Re: Binary tree pattern
Post by Dudidu on Oct 19^th, 2003, 6:24am

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 {1ⁿ0ⁿ| 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:
:)[hide] S = SS || 0S1 || [emptyset] [/hide] :)
p.s. - [hide] [emptyset] stands for null characters.[/hide]

Title: Re: Binary tree pattern
Post by Mike_V on Oct 19^th, 2003, 11:51am

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.

Title: Re: Binary tree pattern
Post by Dudidu on Oct 20^th, 2003, 1:18am

on 10/19/03 at 11:51:21, 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 ;).