The above examples motivate the following definition:

Let $\Sigma$ be an alphabet. A **grammar** (or **syntax** ) is a tuple $G=(V,T,R,S)$ consisting of

- $V\subset\Sigma^*$ a finite set of
**variables**, - $T\subset\Sigma $ a finite set of
**terminal symbols**(or**terminals**), i.e. some special characters from the alphabet $\Sigma$ such that $V\cap T=\emptyset$. - A non-empty, finite set of rules $R$, i.e. pairs $(P,C)\in R$ of
**premises**$P$ and**conclusions**$C$ such that $P\in (V\cup T)^*V (V\cup T)^*$ is a string*containing at least one*variable and $C\in(V\cup T)^*$ is a string. - $S\in V$ as a
**starting symbol**(a first to be replaced terminal symbol)

- A syntax rule $R$ expresses how a string $P$ containing a variable can be transformed into another string $C$.
- Syntax rules can be optional, for instance, $S\to HN$ and $S\to H$ might be two coexisting rules of syntax, replacing the starting variable by the concatenation of $HN$ or only by $H$.
- The (formal) language which is generated by the syntax, consists of all strings that can be generated when applying the ruleset, starting from the
*starting symbol*. - $(V\cup T)^*$ denotes the Kleene star of the union of all variables and all terminals of the grammar. Correspondingly, an element of this union is any (even the empty string) concatenation of variables and terminal symbols.

| | | | | created: 2014-06-22 16:48:32 | modified: 2021-04-11 13:44:39 | by: *bookofproofs* | references: [577]

[577] **Knauer Ulrich**: “Diskrete Strukturen – kurz gefasst”, Spektrum Akademischer Verlag, 2001