# Grammar

Formally, a **grammar** is an ordered fourtuple *G* = (*T,N,S,P*), where *N* and *T* are finite alphabets, *S* is a distinguished symbol of *N*, and *P* is a finite non-empty set pairs (L,R) such that *L* and *R* are in (*N U T*)* and *G* is called a **Context Free Grammar** (CFG) if *L* is in *N*.

The symbols of *N* are called *nonterminal symbols*. The symbols of *T* are called *terminal symbols*. According to above definition of a grammar *G*, the sets *N* and *T* are disjoint in every grammar. The nonterminal symbol *S* is called the initial symbol, axiom or root, and is used to start the derivations of the sentences of the language.

The ordered pairs in *P* are called *rewriting rules* or *productions* and will be written in the form L ---> R where the symbol ---> (derives) is, of course, not in *N U T*. Productions are used to derive new sentences from given ones by replacing a part equal to the left-hand side of a rule by the right-hand side of the same rule.

In such a way, taking always *S* as the starting symbol, it is possible to derive from *S* and just applying productions in *P*, a set (possibly infinite) of sentences that is called the language generated by *G*, *L(G)*.

**See following grammar example:** nLPD grammar