Does a context-free grammar with multiple variables have a “starting” point?

Question

So lets consider the following grammar

$$ \begin{align*} S &\to 0 \mid 0A \\ A &\to 1 \end{align*} $$

would the string "1" be accepted by the language or must the language start with $S$?

Answer 1

No $1$ will not be a part of the grammar, as only those strings generated by starting from the start variable $S$ are part of the grammar.

Answer 2

What you have shown is technically not a grammar, only part of it. A grammar is formally defined as the tuple $(N, \Sigma, P, S)$, where:

• $N$ is a set of non-terminal symbols
• $\Sigma$ is a set of terminal symbols
• $P$ is a set of production rules
• $S$ is a start symbol

You have only provided $P$, but to have a grammar, you also need $N$, $\Sigma$ and $S$.

$N$ and $\Sigma$ are often omitted when defining a grammar, because they are clear from $P$ (like in your example, where $N = \{ S, A \}$ and $\Sigma = \{ 0, 1 \}$).

Explicitly specifying the start symbol (referred to as $S$ in the formal definition above) can be omitted when there is a clear convention for the name of the start symbol; naming it $S$ as you do in your example is a common convention.

What this all means for your example is that if you assume that $S$ is the start symbol, then $1$ is not a member of the language. If you instead assumed that $A$ is the start symbol, then $1$ would be a member of the language. Such grammar would be formally valid, but defining it like this wouldn't make sense from a human's point of view.