startsymbolet

Startsymbolet, called the start symbol in English, is the designated nonterminal in a formal grammar from which every sentence of the language can be derived. It functions as the root of the derivation tree and is where derivations begin. In most textbooks, the start symbol is denoted by S, but the symbol is chosen by the grammar designer and need not be restricted to S.

Formally, a grammar G consists of terminals, nonterminals, production rules, and a start symbol S. The language L(G) is the set of strings of terminal symbols that can be derived from S using zero or more applications of production rules: L(G) = { w in T* | S =>* w }. The start symbol itself is a nonterminal and can appear on the right-hand side of rules. If S =>* epsilon, the empty string is in the language.

Example: A simple context-free grammar with S -> a S b | epsilon has start symbol S. The language is { a^n b^n | n >= 0 }.

Use in parsing: The start symbolet is a central reference point for parsing algorithms (e.g., CYK, LL(1) parsers) and for proving properties of grammars. In some grammars there is a single designated start symbol; other formalisms may allow multiple starting points by introducing a new start symbol that derives several existing nonterminals.

In linguistics and formal language theory, the start symbolet designates the most general sentence form generated by the grammar and provides the root of the parse tree.