Collatz Sequence Recognition

Let L = {a^x b^y c^z | (x is odd in N, y = 3x+1, z = y/2) OR (x is even in
N, y = x/2, z = (y is odd) ? 3y+1 : y/2}


In other words -- let (x, y, z) be some 3-tuple s.t. they are a subset of
some Collatz Sequence. Examples:


aaaabbc (4, 2, 1)
aaabbbbbbbbbbccccc (3, 10, 5)
abbbbcc (1, 4, 2)


Now, assume that rather than a, b, c, we rework it s.t. L_2 = {w_1^x_1
w_2^x_2 ... w_n^x_n | n > 2, sigma = {1,0} s.t. letters of w_i and
w_i+1 mod 2, and x_1 ... x_n are a Collatz sequence}, i.e.:


1111001 (4,2,1)
1110000001111111111000001111111111111111000000001111001 (3,10,5,16,8,4,2,1)
etc.


1. Would anyone here care to formally prove that L/L2 is/are [a] Type 1
language(s), as opposed to Type 0?
2. Would a grammar for such a language be "interesting"?


--
Quinn

Return to the comp.compilers page.
Search the comp.compilers archives again.