3
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Era May 11 '16 at 22:35
  • $\begingroup$ @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. $\endgroup$ – svick May 11 '16 at 22:37
  • $\begingroup$ There is another convention: the head (left-hand side) of the first production rule is the start symbol (which is $S$ in this example). $\endgroup$ – Anton Trunov May 12 '16 at 6:18

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.