Range concatenation grammar

A Positive Range Concatenation Grammar (PRCG) is a tuple $G\; =\; (N,~T,~V,~S,~P)$, where:

• $N$, $T$ and $V$ are disjoint finite sets of (respectively) predicate names, terminal symbols and variable names. Each predicate name has an associated arity given by the function $\backslash dim:\; N\; \backslash rightarrow\; \backslash mathbb\{N\}\backslash setminus\backslash \{0\backslash \}$.
• $S\; \backslash in\; N$ is the start predicate name and verify $\backslash dim(S)=1$.
• $P$ is a finite set of clauses of the form $\backslash psi\_0\; \backslash rightarrow\; \backslash psi\_1\; \backslash ldots\; \backslash psi\_m$, where the $\backslash psi\_i$ are predicates of the form $A\_i(\backslash alpha\_1,\; \backslash ldots,\; \backslash alpha\_\{\backslash dim(A\_i)\})$ with $A\_i\; \backslash in\; N$ and $\backslash alpha\_i\; \backslash in\; (T\; \backslash cup\; V)^\backslash star$.

A Negative Range Concatenation Grammar (NRCG) is defined like a PRCG, but with the addition that some predicates occurring in the right-hand side of a clause can have the form $\backslash overline\{A\_i(\backslash alpha\_1,\; \backslash ldots,\; \backslash alpha\_\{\backslash dim(A\_i)\})\}$. Such predicates are called negative predicates.

A Range Concatenation Grammar is a positive or a negative one. Although PRCGs are technically NRCGs, the terms are used to highlight the absence (PRCG) or presence (NRCG) of negative predicates.

A range in a word $w\; \backslash in\; T^\backslash star$ is a couple $\backslash langle\; l,\; r\; \backslash rangle\_w$, with $0\; \backslash leq\; l\; \backslash leq\; r\; \backslash leq\; n$, where $n$ is the length of $w$. Variables bind to ranges, not to arbitrary strings of nonterminals. Two ranges $\backslash langle\; l\_1,\; r\_1\; \backslash rangle\_w$ and $\backslash langle\; l\_2,\; r\_2\; \backslash rangle\_w$ can be concatenated iff $r\_1\; =\; l\_2$, and we then have: $\backslash langle\; l\_1,\; r\_1\; \backslash rangle\_w\; \backslash cdot\; \backslash langle\; l\_2,\; r\_2\; \backslash rangle\_w\; =\; \backslash langle\; l\_1,\; r\_2\; \backslash rangle\_w$. When instantiating a clause, where an argument consists of multiple elements from $T\; \backslash cup\; V$, their ranges must concatenate.

For a word $w\; =\; w\_1w\_2\backslash ldots\; w\_n$, with $w\_i\; \backslash in\; T$, the dotted notation for ranges is: $\backslash langle\; l,\; r\; \backslash rangle\_w\; =\; w\_1\backslash ldots\; w\_\{l-1\}\; \backslash bullet\; w\_l\backslash ldots\; w\_\{r-1\}\; \backslash bullet\; w\_r\backslash ldots\; w\_n$.

The strings of predicates being rewritten represent constraints that the string being tested has to satisfy (if positive), or in the case of negative predicates not satisfy. The order of predicates is irrelevant. Rewrite steps amount to replacing one constraint by zero or more simpler constraints.

Like LMGs, RCG clauses have the general schema $A(x\_1,\; ...,\; x\_n)\; \backslash to\; \backslash alpha$, where in an RCG, $\backslash alpha$ is either the empty string or a string of predicates. The arguments $x\_i$ consist of strings of terminal symbols and/or variable symbols, which pattern match against actual argument values like in LMG. Adjacent variables constitute a family of matches against partitions, so that the argument $xy$, with two variables, matches the literal string $ab$ in three different ways: $x\; =\; \backslash epsilon,\backslash \; y\; =\; ab;\backslash \; x\; =\; a,\backslash \; y\; =\; b;\backslash \; x\; =\; ab,\backslash \; y\; =\; \backslash epsilon$. These would give rise to three different instantiations of the clause containing that argument $xy$.

Predicate terms come in two forms, positive (which produce the empty string on success), and negative (which produce the empty string on failure/if the positive term does not produce the empty string). Negative terms are denoted the same as positive terms, with an overbar, as in $\backslash overline\{A(x\_1,\; ...,\; x\_n)\}$.

The rewrite semantics for RCGs is rather simple, identical to the corresponding semantics of LMGs. Given a predicate string $A(\backslash alpha\_1,\; ...,\; \backslash alpha\_n)$, where the symbols $\backslash alpha\_i$ are terminal strings, if there is a rule $A(x\_1,\; ...,\; x\_n)\; \backslash to\; \backslash beta$ in the grammar that the predicate string matches, the predicate string is replaced by $\backslash beta$, substituting for the matched variables in each $x\_i$.

For example, given the rule $A(x,\; ayb)\; \backslash to\; B(axb,\; y)$, where $x$ and $y$ are variable symbols and $a$ and $b$ are terminal symbols, the predicate string $A(a,\; abb)$ can be rewritten as $B(aab,\; b)$, because $A(a,\; abb)$ matches $A(x,\; ayb)$ when $x\; =\; a,\backslash \; y\; =\; b$. Similarly, if there were a rule $A(x,\; ayb)\; \backslash to\; A(x,\; x)\backslash \; A(y,\; y)$, $A(a,\; abb)$ could be rewritten as $A(a,\; a)\backslash \; A(b,\; b)$.

A proof/recognition of a string $\backslash alpha$ is done by showing that $S(\backslash alpha)$ produces the empty string. For the individual rewrite steps, when multiple alternative variable matches are possible, any rewrite which could lead the whole proof to succeed is considered. Thus, if there is at least one way to produce the empty string from the initial string $S(\backslash alpha)$, the proof is considered a success, regardless of how many other ways to fail exist.

RCGs are capable of recognizing the non-linear index language $\backslash \{\; www\; :\; w\; \backslash in\; \backslash \{a,b\backslash \}^\{*\}\; \backslash \}$ as follows:

Letting x, y, and z be variable symbols:

$$$$

\begin{aligned}

S(xyz) &\to A(x, y, z) \\

A(ax, ay, az) &\to A(x, y, z) \\

A(bx, by, bz) &\to A(x, y, z) \\

A(\epsilon, \epsilon, \epsilon) &\to \epsilon

\end{aligned}

The proof for {{not a typo|abbabbabb}} is then

$S(abbabbabb)\; \backslash Rightarrow\; A(abb,\; abb,\; abb)\; \backslash Rightarrow\; A(bb,\; bb,\; bb)\; \backslash Rightarrow\; A(b,\; b,\; b)\; \backslash Rightarrow\; A(\backslash epsilon,\; \backslash epsilon,\; \backslash epsilon)\; \backslash Rightarrow\; \backslash epsilon$

Or, using the more correct dotted notation for ranges:

$S(\backslash bullet\{\}abbabbabb\backslash bullet\{\})\; \backslash Rightarrow\; A(\backslash bullet\{\}abb\backslash bullet\{\}abbabb,\; abb\backslash bullet\{\}abb\backslash bullet\{\}abb,\; abbabb\backslash bullet\{\}abb\backslash bullet\{\})\; \backslash Rightarrow\; A(a\backslash bullet\{\}bb\backslash bullet\{\}abbabb,\; abba\backslash bullet\{\}bb\backslash bullet\{\}abb,\; abbabba\backslash bullet\{\}bb\backslash bullet\{\})$ $\backslash Rightarrow\; A(ab\backslash bullet\{\}b\backslash bullet\{\}abbabb,\; abbab\backslash bullet\{\}b\backslash bullet\{\}abb,\; abbabbab\backslash bullet\{\}b\backslash bullet\{\})\; \backslash Rightarrow\; A(\backslash epsilon,\; \backslash epsilon,\; \backslash epsilon)\; \backslash Rightarrow\; \backslash epsilon$

For a string of $3n$ letters, there are $\backslash binom\{3n+2\}\{2\}\; =\; \backslash frac\{(3n+2)(3n+1)\}\{2\}$ different instantiations of that first clause, but only the one which makes $x,y,z$ all $n$ letters each allows the derivation to reach $\backslash epsilon$.

Every context-free grammar (CFG) can be converted into a range concatenation grammar:

• For every nonterminal $A$ of the CFG, the RCG has an arity $1$ predicate $A(x)$.
• For every CFG rule $A\; \backslash to\; BC$, the RCG has $A(xy)\; \backslash to\; B(x)\; C(y)$.
• For every CFG rule $A\; \backslash to\; a$ (where $a$ terminal), the RCG has $A(a)\; \backslash to\; \backslash epsilon$.

The intersection and union of two range concatenation languages are trivially range concatenation languages:

• For $S$ the intersection of $A$ and $B$, you have $S(x)\; \backslash to\; A(x)B(x)$.
• For $S$ the union of $A$ and $B$, you have $S(x)\; \backslash to\; A(x)$ and $S(x)\; \backslash to\; B(x)$.

Possibly negative range concatenation languages are also closed under set complement.

A consequence of the above is that it is undecidable whether a (positive) range concatenation language is nonempty, because it is undecidable whether the intersection of two context-free languages is nonempty. Hence range concatenation grammars are not generative.

{{Formal languages and grammars}}

Category:Formal languages

Category:Grammar frameworks