Given a grammar such as the following, does $S'$ have some special meaning or does it just denote another non-terminal like $B$, $A$, $P$, $Q$ etc.?

$$\begin{align*} S &\to aBS'\\ B &\to b\\ S'&\to bA \end{align*}$$


$S'$ is just another nonterminal.

The reason $S'$ is used instead of, say, $T$, is that $S$ has been established as standard for the start symbol of a grammar. Now, if you are talking about an algorithm that transforms a grammar (e.g. into a normal form), you will need to distinguish between the start symbol of the original grammar and that of the transformed grammar. In order to indicate that both are start symbols, it has become the norm to use $S'$ for one of them (usually the latter).

| cite | improve this answer | |
  • $\begingroup$ in the context of concatenating two CFG's, lets say a language consisting of only $a's$ and a language of strings starting with an a in {a,b}. I will look at the link about LaTex $\endgroup$ – Plengo Aug 20 '14 at 10:53

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.