2

For a context-free grammar G = (V,T,S,P)

If one production rule of G is A -> nBC where n ∈ T*, does it mean that the production rule of the form A -> BC is also allowed?

Since n ∈ T*, can n be empty due to the Kleene star on T (set of terminals)?

stevetronix
  • 433
  • 1
    Only if $n$ is the empty word. In other words, if $T={0,1}$, say, the productions $A\to BC$, $A\to 01BC$, and $A\to 1BC$ all fit the pattern $A\to nBC$ with $n\in T^$, but only the first allows a derivation of $BC$ from $A$. $G$ cannot have a production rule that allows all* productions of this form, because it has to be finite. – Brian M. Scott Jun 04 '15 at 18:07
  • Ok, so T* allows an empty condition for n ∈ T* (which allows for A --> BC, no matter what the set of terminals T is, right? – stevetronix Jun 04 '15 at 18:17
  • 1
    Yes. If you’re taking $A\to nBC$ with $n\in T^*$ as a pattern, rather than as a specific production, then one of the productions fitting that pattern is $A\to BC$, irrespective of what $T$ is. – Brian M. Scott Jun 04 '15 at 18:18

0 Answers0