21 Jun 2004 23:53:24 -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: | Carl Cerecke <cdc@maxnet.co.nz> |

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

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.