Let L be the language over {0,1} consisting of all strings which have
an even number of 1s.  L is given by the regular expression
0*(10*10*)*

We given an O(log(n)) time algorithm for accepting L, using n processors.

We define substrings of w at each height, from 0 up to log n, as follows.

A height 0 substring of w is any substring of length 1.

Consecutive pairs of height h substrings are concatenated to make substrings
of height h+1.  There may be an orphan at the end.

These substrings form a binary tree.
For example, if w = 01000111110101001010110101,
the binary tree of substrings looks like this:


                            01000111110101001010110101

             0100011111010100                         1010110101

        01000111          11010100               10101101            01

      0100     0111     1101      0100        1010      1101       01

     01  00   01  11   11   01   01   00     10   10   11   01   01
    0 1  0 0  0 1 1 1  1 1  0 1  0 1  0 0    1 0  1 0  1 1  0 1  0 1


Now, place one processor at each node of the binary tree.  The job of
this processor is to determine whether there is an even number of 1's
in its substring.  The processors at the bottom each have just one symbol,
so they just look at that symbol.  Processors above the bottom level
wait for reports from the two processors below them, and then pass their
answer upward.  Each processor takes O(1) time, since two evens or two
odds make an even, while an even and an odd make an odd.

There are log(n) levels, so the algorithm takes O(log n) time.