Controlled grammar
Controlled grammars are a class of grammars that extend, usually, the context-free grammars with additional controls on the derivations of a sentence in the language. A number of different kinds of controlled grammars exist, the four main divisions being Indexed grammars, grammars with prescribed derivation sequences, grammars with contextual conditions on rule application, and grammars with parallelism in rule application. Because indexed grammars are so well established in the field, this article will address only the latter three kinds of controlled grammars.
Control by prescribed sequences
Grammars with prescribed sequences are grammars in which the sequence of rule application is constrained in some way. There are four different versions of prescribed sequence grammars: language controlled grammars, matrix grammars, vector grammars, and programmed grammars.In the standard context-free grammar formalism, a grammar itself is viewed as a 4-tuple,, where N is a set of non-terminal/phrasal symbols, T is a disjoint set of terminal/word symbols, S is a specially designated start symbol chosen from N, and P is a set of production rules like, where X is some member of N, and is some member of.
Productions over such a grammar are sequences of rules in P that, when applied in order of the sequence, lead to a terminal string. That is, one can view the set of imaginable derivations in G as the set, and the language of G as being the set of terminal strings. Control grammars take seriously this definition of the language generated by a grammar, concretizing the set-of-derivations as an aspect of the grammar. Thus, a prescribed sequence controlled grammar is at least approximately a 5-tuple where everything except R is the same as in a CFG, and R is an infinite set of valid derivation sequences.
The set R, due to its infinitude, is almost always described via some more convenient mechanism, such as a grammar, or a set of matrices or vectors. The different variations of prescribed sequence grammars thus differ by how the sequence of derivations is defined on top of the context-free base. Because matrix grammars and vector grammars are essentially special cases of language controlled grammars, examples of the former two will not be provided below.
Language controlled grammars
Language controlled grammars are grammars in which the production sequences constitute a well-defined language of arbitrary nature, usually though not necessarily regular, over a set of context-free production rules. They also often have a sixth set in the grammar tuple, making it, where F is a set of productions that are allowed to apply vacuously. This version of language controlled grammars, ones with what is called "appearance checking", is the one henceforth.Proof-theoretic description
We let a regularly controlled context-free grammar with appearance checking be a 6-tuple where N, T, S, and P are defined as in CFGs, R is a subset of P* constituting a regular language over P, and F is some subset of P. We then define the immediately derives relation as follows:Given some strings x and y, both in, and some rule,
holds if either
Intuitively, this simply spells out that a rule can apply to a string if the rule's left-hand-side appears in that string, or if the rule is in the set of "vacuously applicable" rules which can "apply" to a string without changing anything. This requirement that the non-vacuously applicable rules must apply is the appearance checking aspect of such a grammar. The language for this kind of grammar is then simply set of terminal strings.
Example
Consider a simple context-free grammar that generates the language :Let, where
In language controlled form, this grammar is simply . A simple modification to this grammar, changing is control sequence set R into the set, and changing its vacuous rule set F to, yields a grammar which generates the non-CF language. To see how, consider the general case of some string with n instances of S in it, i.e. .
If we chose some arbitrary production sequence, we can consider three possibilities:,, and When we rewrite all n instances of S as AA, by applying rule f to the string u times, and proceed to apply g, which applies vacuously . When, we rewrite all n instances of S as AA, and then try to perform the n+1 rewrite using rule f, but this fails because there are no more Ss to rewrite, and f is not in F and so cannot apply vacuously, thus when, the derivation fails. Lastly, then, we rewrite u instances of S, leaving at least one instance of S to be rewritten by the subsequent application of g, rewriting S as X. Given that no rule of this grammar ever rewrites X, such a derivation is destined to never produce a terminal string. Thus only derivations with will ever successfully rewrite the string. Similar reasoning holds of the number of As and v. In general, then, we can say that the only valid derivations have the structure will produce terminal strings of the grammar. The X rules, combined with the structure of the control, essentially force all Ss to be rewritten as AAs prior to any As being rewritten as Ss, which again is forced to happen prior to all still later iterations over the S-to-AA cycle. Finally, the Ss are rewritten as as. In this way, the number of Ss doubles each for each instantiation of that appears in a terminal-deriving sequence.
Choosing two random non-terminal deriving sequences, and one terminal-deriving one, we can see this in work:
Let, then we get the failed derivation:
Let, then we get the failed derivation:
Let, then we get the successful derivation:
Similar derivations with a second cycle of produce only SSSS. Showing only the successful derivation:
Matrix grammars
Matrix grammars are a special case of regular controlled context-free grammars, in which the production sequence language is of the form, where each "matrix" is a single sequence. For convenience, such a grammar is not represented with a grammar over P, but rather with just a set of the matrices in place of both the language and the production rules. Thus, a matrix grammar is the 5-tuple, where N, T, S, and F are defined essentially as previously done, and M is a set of matrices where each is a context-free production rule.The derives relation in a matrix grammar is thus defined simply as:
Given some strings x and y, both in, and some matrix,
holds if either
Informally, a matrix grammar is simply a grammar in which during each rewriting cycle, a particular sequence of rewrite operations must be performed, rather than just a single rewrite operation, i.e. one rule "triggers" a cascade of other rules. Similar phenomena can be performed in the standard context-sensitive idiom, as done in rule-based phonology and earlier Transformational grammar, by what are known as "feeding" rules, which alter a derivation in such a way as to provide the environment for a non-optional rule that immediately follows it.
Vector grammars
Vector grammars are closely related to matrix grammars, and in fact can be seen as a special class of matrix grammars, in which if, then so are all of its permutations. For convenience, however, we will define vector grammars as follows: a vector grammar is a 5-tuple, where N, T, and F are defined previously, and where M is a set of vectors, each vector being a set of context free rules.The derives relation in a vector grammar is then:
Given some strings x and y, both in, and some matrix,
holds if either
Notice that the number of production rules used in the derivation sequence, n, is the same as the number of production rules in the vector. Informally, then, a vector grammar is one in which a set of productions is applied, each production applied exactly once, in arbitrary order, to derive one string from another. Thus vector grammars are almost identical to matrix grammars, minus the restriction on the order in which the productions must occur during each cycle of rule application.
Programmed grammars
Programmed grammars are relatively simple extensions to context-free grammars with rule-by-rule control of the derivation. A programmed grammar is a 4-tuple, where N, T, and S are as in a context-free grammar, and P is a set of tuples, where p is a context-free production rule, is a subset of P, and is a subset of P. If the failure field of every rule in P is empty, the grammar lacks appearance checking, and if at least one failure field is not empty, the grammar has appearance checking. The derivation relation on a programmed grammar is defined as follows:Given two strings, and some rule,
The language of a programmed grammar G is defined by constraining the derivation rule-wise, as, where for each, either or.
Intuitively, when applying a rule p in a programmed grammar, the rule can either succeed at rewriting a symbol in the string, in which case the subsequent rule must be in ps success field, or the rule can fail to rewrite a symbol, in which case the subsequent rule must be in ps failure field. The choice of which rule to apply to the start string is arbitrary, unlike in a language controlled grammar, but once a choice is made the rules that can be applied after it constrain the sequence of rules from that point on.
Example
As with so many controlled grammars, programmed grammars can generate the language :Let, where
The derivation for the string is as follows:
As can be seen from the derivation and the rules, each time and succeed, they feed back to themselves, which forces each rule to continue to rewrite the string over and over until it can do so no more. Upon failing, the derivation can switch to a different rule. In the case of, that means rewriting all Ss as AAs, then switching to. In the case of, it means rewriting all As as Ss, then switching either to, which will lead to doubling the number of Ss produced, or to which converts the Ss to as then halts the derivation. Each cycle through then therefore either doubles the initial number of Ss, or converts the Ss to as. The trivial case of generating a, in case it is difficult to see, simply involves vacuously applying, thus jumping straight to which also vacuously applies, then jumping to which produces a.