0

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?

beoliver
  • 178

1 Answers1

0

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

Mark
  • 2,535
  • sure, I just wasn't sure about the spaces. So S → A B = S → AB? Does that not become problematic if you have an AB as well as an A and a B? – beoliver Nov 16 '14 at 01:59
  • I've never seen spaces in the production rules of a CFG, so I assume that $S \to A \ B$ with a space between $A$ and $B$ simply means $S \to AB$ with no space. The production rules should not have $A, B, AB$ as variables to avoid confusion. – Mark Nov 16 '14 at 02:00