The Turtle family of formal languages


The language

The Turtle family is the family of formal languages over the alphabet Tt = {F, f, l, r}.

The canvas

The semantic meaning of words over Tt is defined using a turtle canvas c = (t, s), where t is the turtle, defined as t = (p, h) (with p,h∈ℝ²) and s is the set of segments drawn, defined as s⊆{{p₁,p₂}|p₁,p₂∈ℝ²}. The canvas starts in the state ((p₀,h₀), ∅).

Interpreting a word

Each letter of a word over Tt changes the canvas ((p,h),s) according to the following table:

LetterTransformed canvas
f((p+h,h), s)
F((p+h,h), s∪{p, p+h})
l((p,rotate(h,+90°), s)
r((p,rotate(h,-90°), s)

Thus, the interpretation of a word is simply done by transforming the canvas for each letter, and getting the end state ((p',h'),s').

Languages in Turtle

We consider actual languages L over Tt that are described in a simple recursive way, by explicitly defining a single word u₀, and giving a function f mapping from letters of Tt to words over Tt. Hence,

L = {uk∈Tt*|k∈ℕ ∧ uk=∏f(uk-1i)}

For example, consider the following language:

u₀ = FlFlFlFl
f(F) = FlFrFrFFlFlFr

This gives this graph as u₀ and the right-angle Koch islands as u₁, u₂, u₃, u₄,… (click to see them in SVG).

Python implementation

This Python program implements Turtle languages as defined by an initial word and a recursive homomorphism. The output is a set of SVG files.