CFG: Translate English sentence to math basic logic

Question

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

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.