<p>I am trying to find any described formalism which introduces <em>free variables</em> into word grammars (I emphasize here <em>word</em> in order not to be confused with very similar thing in <em>tree</em> grammars).</p>

<p>What I mean is something like this:</p>

<p>$AX_1B\rightarrow AX_1CX_1B$</p>

<p>where $X_1$ can be substituted by any sequence $\alpha$ of terminals and non-terminals ($\alpha\in (T\cup N)^+$).</p>

<p>Say, if our derivation is $AbEdB$, then this rule will give next derivation as:
$AbEdB\Rightarrow AbEdCbEdB$. </p>

<p>More generally, rules of this form can be described as:
$\alpha\rightarrow\beta$, where $\alpha,\beta\in (T\cup N\cup X)+$, where $X=\{X_1,\dots,X_n\}$. For more details, please see the updates below.</p>

<p>It is clear that variables them self do not add anything new into grammars per se. But what I am looking for is existent works which describe how such <em>free variables</em> fit into known classes of grammars. For instance, will such grammar be weak-equivalent to the context-sensitive grammar under some circumstances or not?</p>

<p><strong>UPD</strong>: Answering commentary: $X_i$ is a kind of pattern, so that all $X_i$ can be replaced by regular expression groups. Like in the foregoing example, it is "$A(.+)B$", where $(.+)$ is a named group "$X_1$". In other words, the rule containing $X_i$ variables can be applied if its entire left-hand side string, considered in the mentioned way, conforms as pattern to any substring within the current derivation.</p>

<p><strong>UPD-2</strong>: Answering commentary #2: </p>

<p>1) Each $X_i$ from the left-hand side should  necessarily be present in the right-hand side. </p>

<p>2) Each $X_i$ always represent $(.+)$, i.e. it can not have an empty value.</p>

<p>3) For each rule, set of variables $\{X_i\}$ is unique. So they should not be considered as something spread across several rules.</p>

<p>4) Yes, each rule can contain multiple free-variables. Further more, each $X_i$ can be present in the left-hand side only once, while in the right-hand side more than one time (arbitrary number of times, but not zero).</p>

<p>5) There are no any restrictions on the variables order. They can have arbitrary order as in the left-hand side, so as in the right-hand side (i.e. the rule $AX_1BX_2C→DX_2EX_1F$ is valid).</p>

CC BY-SA 3.0
2017-11-27T13:11:00.800Z
After thinking about it; even if you force $X_i$ in each rule; something like $X_i ABC \to X_i DEF$, $X_i = (.)^+$ is definitively equivalent to $ABC \to DEF$ up to some prefix symbol (^) that could be added to the CS language and used to match $\text{^}ABC $  and could be avoided if $X_i = (.)^*$.
Marzio De Biasi
CC BY-SA 3.0
2017-11-22T11:40:35.970Z
Can you describe your model of grammars with "free variables" more accurate? If a "free variable" $X$ is just a variable in the sense that you can replace it with an arbitrary word, then isn't this equivalent to a grammar where $X$ is a nonterminal which evaluates to $T^*$?
Danny
CC BY-SA 3.0
2017-11-22T11:51:04.007Z
@Danny I've added an update to my question. Hope it explains somehow more my insight.
Andrey Lebedev
CC BY-SA 3.0
2017-11-23T08:52:08.903Z
Some clarification needed. Can you have a rule in which there is a $X_i$ on the left side, but no $X_i$ on the right side (kind of elimination)? Do all $X_i$ represent $(.+)$ ? Can you have multiple free variables in the same rule? Can free variables be mixed among the rules ?
Marzio De Biasi
CC BY-SA 3.0
2017-11-23T08:57:34.517Z
@MarzioDeBiasi is that a reason for downvoting?
Andrey Lebedev
CC BY-SA 3.0
2017-11-23T09:17:07.273Z
@AndreyLebedev: It is still unclear if a rule can contain more than one $X_1, X_2, ...$ in the left side that in the right part can be rearranged (e.g $AX_1BX_2C \to DX_2 E X_1F$. BTW I didn't downvote your question :-D BTW2 Your question has no downvotes (at the present time).
Marzio De Biasi
CC BY-SA 3.0
2017-11-23T09:20:38.463Z
@MarzioDeBiasi yes, variables can be rearranged in the right-hand side, I don't see any issue with this. And thanks for clarifying voting point :)
Andrey Lebedev
CC BY-SA 3.0
2017-11-23T09:31:03.010Z
Some thoughts. Clearly with the actual formulation (no limits on the length of the left/right sides) the variant with free variables is equivalent to context sensitive grammars (just avoid the use of $X_i$ in the rules). It still has the power of CS grammars if you add the constraint that left side must contain at least a $X_i$: you can use a special non terminal $Z \to  \$$ as "$X_i$ annihilator": $X_iABC \to X_i Z DEF$ (informal idea: the derived strings have the format $\langle\text{ some garbage }\rangle \$^+ w$ where $w$ is a string that can be generated by a CS grammar).
Marzio De Biasi
CC BY-SA 3.0
2017-11-23T09:33:38.653Z
@MarzioDeBiasi I thought about the same "annihilator" in the same way, but I can not prove yet an equivalency of such formalism to the CS. That is why I decided to ask here, as this idea should be probably being considered by someone else before
Andrey Lebedev
CC BY-SA 3.0
2017-11-23T10:08:30.297Z
Ok, I'll try to think more about it and post a more formal proof as soon as I have some time.
Marzio De Biasi
<grammars>
Word grammars with free variables
Andrey Lebedev
# Word grammars with free variables

(Asked by: username_0 on 2017-11-15)

I am trying to find any described formalism which introduces *free variables* into word grammars (I emphasize here *word* in order not to be confused with very similar thing in *tree* grammars).

What I mean is something like this:

$AX\_1B\rightarrow AX\_1CX\_1B$

where $X\_1$ can be substituted by any sequence $\alpha$ of terminals and non-terminals ($\alpha\in (T\cup N)^+$).

Say, if our derivation is $AbEdB$, then this rule will give next derivation as:
$AbEdB\Rightarrow AbEdCbEdB$.

More generally, rules of this form can be described as:
$\alpha\rightarrow\beta$, where $\alpha,\beta\in (T\cup N\cup X)+$, where $X=\{X\_1,\dots,X\_n\}$. For more details, please see the updates below.

It is clear that variables them self do not add anything new into grammars per se. But what I am looking for is existent works which describe how such *free variables* fit into known classes of grammars. For instance, will such grammar be weak-equivalent to the context-sensitive grammar under some circumstances or not?

**UPD**: Answering commentary: $X\_i$ is a kind of pattern, so that all $X\_i$ can be replaced by regular expression groups. Like in the foregoing example, it is "$A(.+)B$", where $(.+)$ is a named group "$X\_1$". In other words, the rule containing $X\_i$ variables can be applied if its entire left-hand side string, considered in the mentioned way, conforms as pattern to any substring within the current derivation.

**UPD-2**: Answering commentary #2:

1) Each $X\_i$ from the left-hand side should necessarily be present in the right-hand side.

2) Each $X\_i$ always represent $(.+)$, i.e. it can not have an empty value.

3) For each rule, set of variables $\{X\_i\}$ is unique. So they should not be considered as something spread across several rules.

4) Yes, each rule can contain multiple free-variables. Further more, each $X\_i$ can be present in the left-hand side only once, while in the right-hand side more than one time (arbitrary number of times, but not zero).

5) There are no any restrictions on the variables order. They can have arbitrary order as in the left-hand side, so as in the right-hand side (i.e. the rule $AX\_1BX\_2C→DX\_2EX\_1F$ is valid).

**Tags:** grammars
> **Comments:**
> **username_2**: Can you describe your model of grammars with "free variables" more accurate? If a "free variable" $X$ is just a variable in the sense that you can replace it with an arbitrary word, then isn't this equivalent to a grammar where $X$ is a nonterminal which evaluates to $T^*$?  
> **username_0**: @Danny I've added an update to my question. Hope it explains somehow more my insight.  
> **username_1**: Some clarification needed. Can you have a rule in which there is a $X_i$ on the left side, but no $X_i$ on the right side (kind of elimination)? Do all $X_i$ represent $(.+)$ ? Can you have multiple free variables in the same rule? Can free variables be mixed among the rules ?  
> **username_0**: @MarzioDeBiasi is that a reason for downvoting?  
> **username_1**: @AndreyLebedev: It is still unclear if a rule can contain more than one $X_1, X_2, ...$ in the left side that in the right part can be rearranged (e.g $AX_1BX_2C \to DX_2 E X_1F$. BTW I didn't downvote your question :-D BTW2 Your question has no downvotes (at the present time).  
> **username_0**: @MarzioDeBiasi yes, variables can be rearranged in the right-hand side, I don't see any issue with this. And thanks for clarifying voting point :)  
> **username_1**: Some thoughts. Clearly with the actual formulation (no limits on the length of the left/right sides) the variant with free variables is equivalent to context sensitive grammars (just avoid the use of $X_i$ in the rules). It still has the power of CS grammars if you add the constraint that left side must contain at least a $X_i$: you can use a special non terminal $Z \to  \$$ as "$X_i$ annihilator": $X_iABC \to X_i Z DEF$ (informal idea: the derived strings have the format $\langle\text{ some garbage }\rangle \$^+ w$ where $w$ is a string that can be generated by a CS grammar).  
> **username_0**: @MarzioDeBiasi I thought about the same "annihilator" in the same way, but I can not prove yet an equivalency of such formalism to the CS. That is why I decided to ask here, as this idea should be probably being considered by someone else before  
> **username_1**: Ok, I'll try to think more about it and post a more formal proof as soon as I have some time.  
> **username_1**: After thinking about it; even if you force $X_i$ in each rule; something like $X_i ABC \to X_i DEF$, $X_i = (.)^+$ is definitively equivalent to $ABC \to DEF$ up to some prefix symbol (^) that could be added to the CS language and used to match $\text{^}ABC $  and could be avoided if $X_i = (.)^*$.  

---

## 0 answers

