Context sensitive?

Let the developers know what you think of the software and what can be done to either improve the CFDG language or the Context Free program.

Moderators: MtnViewJohn, chris, mtnviewmark

Post Reply
Tegiri_Nenashi
Posts: 9
Joined: Wed May 14, 2008 12:52 pm

Context sensitive?

Post by Tegiri_Nenashi »

Apparently, Chris moved into context sensitive domain so I wonder how he did it :)

In general, when referring to formal grammars and languages area one have to identify operations such as word concatenation and alternative choice (among grammar rules with the same LHS). Identifying operations is something that IMO should be done before arguing if a model is context free, or sensitive, or else.

OK, let's reduce CFDG to bare essentials -- that would make theoretical investigation easier. Assume there is no color and gray gradients, so we have a plane with black and white pixels only. Then, any shape is a set of points (err, pixels). There are two operations on such shapes:

* union
* affine transformations

In formal languages and grammars speak the union corresponds to alternative choice of grammar rule, and composition of affine transformations corresponds to word concatenation.

So far so good. Union is commutative and associative, and affine transformations form a group. I'm happy to see that we have Kleene algebra as a foundation for the often cited grammar analogy.

Now, let's go back to CFDG. We have color and Z ordering of shapes. The operation of shape superposition (that is "draw a shape, then draw another shape on top of it") is no longer a union, and it is not even commutative! Language analogy breaks.

Finally, let's move to the main issue: How context sensitive rule may look in reduced black-and-white model? The rule has to be something like:

Matrix1 * my_shape * Matrix2 <- Matrix3 * Matrix4 * Matrix5

But then, remember affine transformations (and corresponding matrices) form a group, so one can easily reformulated the above rule by multiplying by inverse matrices:

my_shape <- Matrix1^-1 * Matrix3 * Matrix4 * Matrix5 * Matrix2^-1

In formal languages area we have semigroup instead of a group so the above trick doesn't work. So, is there such a thing as "context sensitive" DG?

Post Reply