-3
$\begingroup$

Consider rules as they are used for context-sensitive languages:

$\alpha A \beta \rightarrow \alpha \gamma \beta$

If $\alpha$ is always empty, we have right-context sensitive grammars:

$A \beta \rightarrow \gamma \beta$

So $\beta$ is here the context. But now consider rules of the form

$A \beta \rightarrow \gamma$

(We are now beyond context-sensitive languages.) Is there a name for this $\beta$? It is not a context, but almost. I am particularly interested if $\beta$ is restricted to zero, one or more terminals.

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ If the β part changes by applying this rewriting rule, what do you mean by saying that it consists of terminals? It does not look like a context to me at all. I would just call β “the string obtained by dropping the first symbol from the left-hand side of a rewriting rule.” $\endgroup$
    – Tsuyoshi Ito
    Oct 19, 2012 at 22:13
  • 2
    $\begingroup$ I did not say “dropping β” at all. β is just one of the substrings of LHS of a rewriting rule, and it does not have any special meaning. $\endgroup$
    – Tsuyoshi Ito
    Oct 20, 2012 at 14:00
  • 2
    $\begingroup$ Unless I'm missing something, if you allow β to be the empty string, your rules are equivalent to the rules of an unrestricted grammar. $\endgroup$
    – Antonio Valerio Miceli-Barone
    Oct 24, 2012 at 1:39
  • 2
    $\begingroup$ @Antonio Valerio Miceli-Barone: No. If β is empty, then the rule is of the form A→γ, that is, context-free. If β is nonempty, then the rule can be essentially anything. $\endgroup$
    – Tsuyoshi Ito
    Oct 26, 2012 at 17:30
  • 2
    $\begingroup$ Perhaps, undrstanding your intention of seeking a name for this could help better in giving a sensible answer. So, what's the context of your question? Perhaps, more info about "Definite Clause Grammar", which you have mentioned, would clarify your question. The correct general answer has already been given by Tsuyoshi Ito. $\endgroup$
    – imz -- Ivan Zakharyaschev
    Oct 27, 2012 at 1:15

1 Answer 1

Reset to default
9
$\begingroup$

In a rule Aβ→γβ, β is called the context because it does not change by applying the rule. Applying a rule Aβ→γ changes the β part completely, and therefore β is not a context at all. In this case, β does not have a name. It is nothing more than one of the many substrings of the left-hand side of the rule Aβ→γ.

If I have to call β as something, I would just call it “the string obtained by dropping the first symbol from the left-hand side of the rule.” In a comment, you stated that this name does not convey your intent, but it is natural because you did not explain your intent. If β has a special meaning in your paper (or whichever use cases that you have in mind), then you should probably come up with a name which describes that special meaning concisely.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ @false: Then my phrasing satisfies your criteria because it does not use the operationalized view of the grammar rule. $\endgroup$
    – Tsuyoshi Ito
    Oct 21, 2012 at 11:16
  • 3
    $\begingroup$ @false: I already explained why β is not a context. It is fine if you want to ignore my answer, but if you do not take answers seriously, I just wonder why you asked a question in the first place. $\endgroup$
    – Tsuyoshi Ito
    Oct 21, 2012 at 12:20
  • 5
    $\begingroup$ @false: (1) I already explained why your notion does not have a name: the notion is not important enough to have a name. Result: you complained that what I wrote is not a name. (2) I already explained why “context” is not a suitable word for your notion. Result: you stated your current candidates, all of which refer to your notion as certain context. It is clear that you did not take my answer seriously. Good luck with other people. $\endgroup$
    – Tsuyoshi Ito
    Oct 22, 2012 at 13:53