For example, given rules $\{ a \to x, a \to y \}$ and input $aa$ , I am usually allowed to derive strings $\{ xx, xy, yx, yy \}$. I would like to restrict this to only performing "consistent" rewrites, so that the language would be like $\{ xx, yy \}$. It is evidently possible to synchronize rewrites in distant parts of a sentence within the usual formal grammar setting, but I wonder if this possibility is better explored under a different name or in a different arrangement.

I notice that context-sensitive grammars pose trouble with this "consistency" condition. For example, given a ruleset $\{ aa \to x\}$ and initial string $aaa$, I am not sure if I should allow anything to be derived. Then again, it is entirely possible that only some rules, and specifically some context-free rules, may be enhanced with consistency.

I am rather sure the system I have in mind defines a language, and even that I could with some thinking propose a formal way to rewrite a given grammar so that some select context free rules are made consistent. But I wonder if this is actually widely known under some other name.


1 Answer 1


Usually, grammar systems where the rules have to be applied in parallel, are called L systems, after the theoretical biologist Aristid Lindenmayer who observed that development in plants must change cells in parallel.

The first example at wikipedia has rules : (A → AB), (B → A), and the string (= line of cells) develop as follows: A → AB → ABA → ABAAB → ABAABABA → ...

Note that in replacing the letters we actually apply a string homomorphism. I think that formally such a system is called D0L-system, with 0 (for zero) to indicate the rules are applied in a context-free manner, i.e., without looking at the neighbours, and D for determinism, in the sense that the mapping applied is a homomorphism, and not a finite substitution.

If one wants to choose between different homomorphisms at various steps of the derivation, we can choose between different homomorphisms. Such a system is usually called DT0L-system, where the T is for tabled: each homomorphism is a table to choose from.

The first DT0L example I could online find, is from the article L Systems by Kari, Rozenberg and Salomaa. Its tables are Td = [a → b, b → bb, c → a] and Tn = [a → c, b → ac, c → c]. In each step we can choose between the two tables.

Starting with a we get b (in both cases) then bb or ac, then bbbb, acac, ba, cc, then b$^8$, acacacac, baba, cccc, bbb, acc, aa and then cc (but that was already generated). Und so weiter und so fort.

PS. An homomorphism (in language theory) is specified as a letter to string mapping, like [a → c, b → ac, c → bb], and then extended to strings, following the mapping letter-by-letter, so aabac → ccaccbb. A finite substitution axtends this by allowing choice in each of the images of the letters, then a letter (and consequently a string) is mapped to a set of strings. Example [a → aa,c ; b → ε,ac,bb]. Now aba maps to the set aaaa, aac, caa, cc, aaacaa, aaacc, cacaa, cacc, aaabba, aabbc, cbbaa, cbbc. I think.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.