Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

closed as not a real question by Kaveh Nov 1 '12 at 20:50

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

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.” – Tsuyoshi Ito Oct 19 '12 at 22:13
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. – Tsuyoshi Ito Oct 20 '12 at 14:00
Unless I'm missing something, if you allow β to be the empty string, your rules are equivalent to the rules of an unrestricted grammar. – Antonio Valerio Miceli-Barone Oct 24 '12 at 1:39
@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. – Tsuyoshi Ito Oct 26 '12 at 17:30
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. – imz -- Ivan Zakharyaschev Oct 27 '12 at 1:15

In a rule γβ, β is called the context because it does not change by applying the rule. Applying a rule γ 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 γ.

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.

share|cite|improve this answer
@false: Then my phrasing satisfies your criteria because it does not use the operationalized view of the grammar rule. – Tsuyoshi Ito Oct 21 '12 at 11:16
@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. – Tsuyoshi Ito Oct 21 '12 at 12:20
@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. – Tsuyoshi Ito Oct 22 '12 at 13:53