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

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

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.

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.

• I'm confused about this sentence: "$S$ can be omitted, if you have a convention for what is the name of the start symbol, naming it $S$ ..." Isn't $S$ the start symbol? How is it being omitted if there is a start symbol called $S$? – Era May 11 '16 at 22:35
• @Era Yeah, that is confusing. $S$ is here used in two different ways: as a variable used to refer to the start symbol and as a symbol itself. Not sure how to make it more clear, while still using the same variable names as the Wikipedia article I linked to. – svick May 11 '16 at 22:37
• There is another convention: the head (left-hand side) of the first production rule is the start symbol (which is $S$ in this example). – Anton Trunov May 12 '16 at 6:18