# How do I call a system like a grammar, but where a rule has to be applied to all matches at once?

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.

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.