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).

  • $\begingroup$ 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^*$? $\endgroup$
    – Danny
    Nov 22, 2017 at 11:40
  • $\begingroup$ @Danny I've added an update to my question. Hope it explains somehow more my insight. $\endgroup$ Nov 22, 2017 at 11:51
  • $\begingroup$ 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 ? $\endgroup$ Nov 23, 2017 at 8:52
  • $\begingroup$ @MarzioDeBiasi is that a reason for downvoting? $\endgroup$ Nov 23, 2017 at 8:57
  • $\begingroup$ @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). $\endgroup$ Nov 23, 2017 at 9:17


Your Answer

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

Browse other questions tagged or ask your own question.