Re: Collatz Sequence Recognition

Quinn Tyler Jackson wrote:
> 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}
[snip]
> 1. Would anyone here care to formally prove that L/L2 is/are [a] Type 1
> language(s), as opposed to Type 0?


Well, I can build a DFA with two stacks that will recognise L with the
following restrictions on the DFA:
1. There is only one stack symbol. This reduces both stacks to merely
counters, with increment and decrement operations.
2. All state transitions are decided by the next input symbol. i.e. the
stack (counters) need not be consulted. Although, of course, popping an
empty stack (decrementing a counter at zero) is an error, and the stacks
have to be empty (counters at zero) in a final state for acceptance.


Where this fits in the language hierarchy, I'm not too sure.


> 2. Would a grammar for such a language be "interesting"?


Only to language/parser/grammar geeks.


Cheers,
Carl Cerecke.

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