Wiki describes the binary relation $\underset{\mbox{G}}{\implies}$ as "G derives in one step". I have a question on the condition when there are multiple productions for a single non-terminal.

Wiki defines $G = (N, \Sigma, P, S)$ and $\underset{\mbox{G}}{\implies} \subset (\Sigma \cup N)^* \times (\Sigma \cup N)^*$ where:

$(\underset{\mbox{G}}{x \implies y}) \iff \exists u,v,p,q \in (\Sigma \cup N)^* : (x = upv) \land ((p, q) \in P) \land (y = uqv)$

Then $(\overset * {\underset{\mbox{G}}{x \implies y}})$ is defined as the refexive transitive closure. Therefore applying $\underset{\mbox{G}}{\implies}$ multiple times results in the language of the grammar:

$\{w \in \Sigma^* | (\overset * {\underset{\mbox{G}}{S \implies w}})\}$


For the form $(\underset{\mbox{G}}{x \implies y})$ I consider the case of multiple rules $(p,q_0), (p, q_1) \in P$ for a non-terminal $N$. If solving for $y$, $y$ will result in the string with only a single rule applied. How should the derivation happen with multiple production rules?

I can see that supplying both arguments $(\Sigma \cup N)^* \times (\Sigma \cup N)^*$ to $\underset{\mbox{G}}{x \implies y}$ will yield all derivations.

  • $\begingroup$ Nothing special happens when there are multiple rules with the same nonterminal. In fact, it is quite common. Indeed, if every nonterminal had a single rule, then the grammar would generate a single word (or no word at all). $\endgroup$ – Yuval Filmus Feb 17 at 21:12

You seem to be looking for a deterministic procedure that isn't there.

With multiple production rules, you solve in every possible way. For instance, for the grammar

$S \rightarrow a \\ S \rightarrow aS$

we have

$ \underset{G}{S \implies a}, \\ \underset{G}{S \implies aS}, \\ \underset{G}{aS \implies aa}, \\ \underset{G}{aS \implies aaS}, \\ \ldots $

  • $\begingroup$ Perhaps the solution is to get all the derivations for a particular $x \in (\Sigma \cup N)$. $Derv_x= \{y | y \in (\Sigma \cup N) \land (\underset{\mbox{G}}{x \implies y})\}$. I think my confusion was the size of the set for $x$ values. $\endgroup$ – Nick Feb 17 at 22:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.