14 Jun 2004 17:45:06 -0400

Related articles |
---|

Collatz Sequence Recognition quinn-j@shaw.ca (Quinn Tyler Jackson) (2004-06-14) |

Re: Collatz Sequence Recognition cdc@maxnet.co.nz (Carl Cerecke) (2004-06-21) |

Re: Collatz Sequence Recognition cdc@maxnet.co.nz (Carl Cerecke) (2004-06-28) |

From: | Quinn Tyler Jackson <quinn-j@shaw.ca> |

Newsgroups: | comp.compilers |

Date: | 14 Jun 2004 17:45:06 -0400 |

Organization: | Compilers Central |

Keywords: | parse, theory, question |

Posted-Date: | 14 Jun 2004 17:45:06 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.