4
$\begingroup$

There is a grammar that describes the walks of a turtle around Manhattan, such that the turtle always returns home. It is described in the book "Parsing Techniques" by Dick Grune and Ceriel J.H. Jacobs, page 18. Unfortunately, I could not find a source online, but the rules are rather simple:

$$ G = \left\langle \{0\}, \Sigma = \{N, S, E, W\}, R, 0 \right\rangle \\[2ex] R = \left\{ \begin{align} & 0 \to N 0 S \\ & 0 \to E 0 W \\ & 0 \to \epsilon \\[2ex] & N S \to S N \\ & \dots \quad \scriptsize{(\text{11 other pairs of distinct } \sigma, \tau \in \Sigma)} \end{align} \right.$$

I actually went ahead and generated some sentences of this grammar. Example:

$$ NENNEENSWWSWSS $$

(Sentence № 10617)

A sentence such as this one corresponds to a graph, like the following:

+-----------------+
|                 |
|                 |
|              *  |
|              ⭣  |
|      * ⭠ * ⭠ *  |
|      ⭣          |
|  * ⭠ *          |
|  ⭣   ⭡          |
|  * ⭢ *          |
|  ⭣              |
|  +              |
|                 |
|                 |
+-----------------+

(Or, rather, to a path on the square lattice of Manhattan, but a path defines a subgraph.)

As this example shows, the walk of our turtle will sometimes have loops.

 

How hard would it be to compose a grammar that generates exactly the acyclic walks?

P.S. As pointed out in comments, there will always be at least one cycle. Let us call that cycle "trivial" and say "a grammar that generates exactly the walks with only the trivial cycle" instead.

$\endgroup$
  • $\begingroup$ If the path starts and ends at the same point (by definition of the grammar), what do you mean by acyclic? If the turtle returns home won't it always be a cyclic path? $\endgroup$ – ryan Sep 30 at 22:59
  • $\begingroup$ @ryan True. Let us say "not non-trivially cyclic" instead. $\endgroup$ – Ignat Insarov Oct 1 at 8:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.