Re: Collatz Sequence Recognition

Carl Cerecke <>
21 Jun 2004 23:53:24 -0400

          From comp.compilers

Related articles
Collatz Sequence Recognition (Quinn Tyler Jackson) (2004-06-14)
Re: Collatz Sequence Recognition (Carl Cerecke) (2004-06-21)
Re: Collatz Sequence Recognition (Carl Cerecke) (2004-06-28)
| List of all articles for this month |

From: Carl Cerecke <>
Newsgroups: comp.compilers
Date: 21 Jun 2004 23:53:24 -0400
Organization: TelstraClear
References: 04-06-060
Keywords: parse
Posted-Date: 21 Jun 2004 23:53:24 EDT

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}
> 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.

Carl Cerecke.

Post a followup to this message

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