in reply to Re: Closed geometry: a train track problem
in thread Closed geometry: a train track problem

In regards to the "grammar" approach, perhaps it's just the Perl background many of us have (regexes do rule!), but that wouldn't address tracks of different radii, which at least exist in the Lionel world. I don't think regexen apply. Maybe they do, but they seem to be one-dimensional. I am thinking (really roughly) that interesting tracks might be built via finite automata... i.e. Conway's game of life on steroids.
  • Comment on Re^2: Closed geometry: a train track problem

Replies are listed 'Best First'.
Re^3: Closed geometry: a train track problem
by Dr. Mu (Hermit) on Jan 03, 2006 at 21:09 UTC
    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.

[reply]
      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]
Re^3: Closed geometry: a train track problem
by Anonymous Monk on Jan 03, 2006 at 21:09 UTC
    I need to add that your grammar is really nifty, and it would produce perfectly valid layouts...and on further review the idea of transformations on a basic pattern is exactly what you proposed. Sorry for misinterpreting -- entirely my fault. However I still wonder how you take that grammar and extend it into 2 and 3D, which as I recall requires some notion of state. My Finite Automata class is a bit rusty, so I forget the term... but I think I'm thinking of this being "not well formed" or "non-homogenous" or some other such phrase. Basically indicating transformations and rules that couldn't be reduced into grammars because of notion of state or other conditions. Darn, I hate forgetting college so fast :)
[reply]
      I in-fact meant "context-free" as you used above. I really should register an account so I can edit things. The idea of building things from transformations does make sense now, especially if you forget coordinates... it would be a fun project.
[reply]

In Section Seekers of Perl Wisdom