I need help making sure the notations below matches the English sentence.

$X_i$ is called an instantiated node in its definition below:

Given a derivation of some context free grammar:

$D = \alpha_0 \implies \dots \implies \alpha_i \implies \alpha_{i+1} \implies \dots \implies \alpha_n$

  • any strings of $\alpha_i$ can be re-written (or $\implies$) to $\alpha_{i + 1}$
    • if there exist a production $X \rightarrow \gamma$
      • and $\alpha_i$ has a form of: $\beta X \delta$ and also $\alpha_{i+1}$ has a form of: $\beta \gamma \delta$

Note that the reason I used both $X$ and $X_i$ is to indicate they are different but related. $X_i$ is a non-terminal belonging to a particular $\alpha_i$, whereas $X$ which is a generic non-terminal and LHS of production $X \rightarrow \gamma$

$\forall i \in [0, n-1] ((\alpha_i \implies \alpha_{i + 1} \in D) \implies (\exists p = X \rightarrow \gamma ( \alpha_i = \beta X_i \delta \wedge \alpha_{i+1} = \beta \gamma \delta )))$


1 Answer 1


A few comments, but too long for a comment box:

  1. The use of $X$ and $X_i$ is (at least) confusing, because they are precisely the same non-terminal. A subscripted variable such as $X_i$ would normally be used as part of a definition of a sequence of objects (as you do with $\alpha_i$), and it's possible that your ultimate goal is to define such a sequence ("instantiated" non-terminals). However, this is not the way to do that.

    $\exists X$ is pretty similar to a programming construct which binds a variable to a value, such as a declaration. In English, we might say something like "At least one person, let's call them Bert, has the following characteristics:. …". This does not define a set of Berts; it just provides a name by which we can talk about the hypothetical individual we are describing. You'd use a different formulation to define the class ("We'll call people with the following characteristics bertical") and yet a different formulation to define an ordered list with reference to some other sequence ("In each municipality, the person who scores highest is named Bertician of that municipality..."). These are evidently different concepts, and not just as an artefact of English grammar.

    Also, I'm more used to seeing letters near the beginning of the alphabet used for non-terminals, FWIW. But I don't suppose it makes much difference.

  2. $\exists p=X\to \gamma$ should be something like $\exists X,\gamma(X\to\gamma \in R)$. Although you might also want to specify that $X\in V$ and $\gamma\in\Sigma^*$. (Here, I'm using the same naming convention as wikipedia, although there are other options.)

  3. Don't mix up $\implies$ and $\to$. $\to$, which is pronounced "derived" in this context, is part of a production (which, as above, is an element of the set of production rules $R$) and is also used to write derivation steps. (It's often used with the Kleene star, $\to^*$, to indicate the result of zero or more derivation steps.) $\implies$, "implies", is a logical assertion.

  4. As you've defined it, $D$ is not a set, so it's not appropriate to use $\in$. (You could define a derivation as a set in several ways, not all of which are sets of productions. But these alternative views of a derivation are probably not useful here.) Since you've already defined $D$ as being the derivation sequence $S\to\alpha_1\to\alpha_2\to\dots\to\alpha_n$ (I changed $\alpha_0$ to $S$ since a derivation always starts with $S$), and that also defines $\alpha_i$, it's sufficient to say $$\alpha_i\to\alpha_{i+1}\implies \exists X, \gamma, \beta, \delta (X\to\gamma\in P \land \alpha_i=\beta X\delta \land \alpha_{i+1}=\beta\gamma\delta)$$.

Since IANAM, there are probably other things which people who are mathematicians would do better. But it's a start.

  • 1
    $\begingroup$ I want to upvote your post for your (correct) points (2) and (3), but I will do so only if you fix your wrong point (1). It is not just confusing to use "$X$" and "$X_i$" but actually outright wrong, so you need to say so. The asker needs to understand the meaning of nested quantifiers properly, not resort to wrong notation to attempt to take over their job. Also, you should amend point (4) because it is not necessarily correct that $D$ is not a set. You could represent $D$ as a set of transitions. Your approach is best, but it's not impossible to do it with $D$ as a set. $\endgroup$
    – user21820
    Aug 29, 2021 at 9:18
  • $\begingroup$ @user21820 maybe instead of $X_i$ I should have used $(X, i)$ to indicate a pair of $X$ belonging to a particular $\alpha_i$ $\endgroup$
    – Node.JS
    Aug 29, 2021 at 15:46
  • 1
    $\begingroup$ @Node.JS: Sorry, but I don't believe you can currently write a correct formal logical statement, regardless of whatever notion you have in mind now. As I advised you in chat, you must learn basic FOL first, including what precisely variables and quantifiers mean, before even attempting to express statements about more complicated things like context-free grammars. $\endgroup$
    – user21820
    Aug 29, 2021 at 16:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .