I am working with context free grammars and have a question concerning the production rules. I have read that the rules are formalized as pairs (α,β) ∈ R. The natural language rules that I am working with are of the form:
S → A B,
B → C D E,
D → foo
does this mean that (S,A B) ∈ R? Should the A B be a pair as well? (S,(A,B)) ∈ R
The only examples I have seen (wikepeadia) were of the form:
S → A,
S → B,
This makes sense in relation to pairs, (S,A) ∈ R, (S,B) ∈ R
But surely
S → A | B is something different to S → A B?
$S \to A \mid B$ means that both $(S,A) \in R$ and $(S,B) \in R$. However, if $S \to AB$, meaning that $S$ produces the string $AB$, then $(S,AB) \in R$.