Re^3: Closed geometry: a train track problem

At the risk of being pedantic, I should point out that there's an equivalence between regular expressions and finite automata. It's this: Sentences in any regular grammar (i.e. one whose rules consist solely of a regular expression) can be parsed by a finite automaton.

What you're referring to with Conway's Game of Life is a cellular automaton. This is a possibly infinite automaton with local transformation rules that could be (and are in Conway's case) regular.

The grammar I describe is neither a regular grammar, nor a context-free grammar (whose sentences can be parsed by adding a stack to a finite state automaton), but a transformational grammar, which requires the full power of a Turing machine to parse.

As to tracks of different radii, they can indeed be accomodated by the grammar approach by assigning unique symbols to curves of each length and radius.

Comment on Re^3: Closed geometry: a train track problem

Replies are listed 'Best First'.
Re^4: Closed geometry: a train track problem by Anonymous Monk on Jan 03, 2006 at 21:11 UTC
See my post below, I briefly had my terminology totally blown and was confusing the grammar you proposed (totally valid) and what I proposed (the exact same thing) with the idea of a regular expression solution ... which was the result of skimming your post waaaay too fast. We are talking about the same thing, I agree -- as I said below, my fault!	[reply]