introduction to grammar

A grammar is a set of rules which are used to construct a language (combine words to generate sentences).
Definition: A grammar is a quadruple (?, V, S, P), where:
1. ? is a finite nonempty set called the terminal alphabet. The elements of ? are called the terminals.

2. V is a finite nonempty set disjoint from ?. The elements of V are called the nonterminals or variables.

3. S ? V is a distinguished nonterminal called the start symbol.

4. P is a finite set of productions (or rules) of the form

???

where ? ? (?UV )*V (?UV )* and ? ? (?UV )*, i.e. ? is a string of terminals and nonterminals containing at least one nonterminal and ? is a string of terminals and nonterminals.
The Language of the Grammar:

If G(V, T, P, S) is a CFG, then the language of G is L(G) = {w in T* | S?(??* ) G w} i.e., the set of strings over T derivable from the start symbol. If G is a CFG, then L(G) a context-free language.

Derivation:
A derivation is a sequence of rewriting operations that starts with the string ? = S and then repeats the following until ? contains only terminals.

A left-most derivation(?(??lm )) is one in which the left-most non-terminal is always chosen as the next non-terminal to expand(Always replace the left-most variable by one of its rule-bodies).

A right-most derivation(?(??rm )) is one in which the right-most non-terminal is always chosen as the next non-terminal to expand(Always replace the rightmost variable by one of its rule-bodies).

?*is the transitive closure of ?. If ??*? holds, then ? can be derived to ?. The sequence ?? • • • ??• • • ?? is called the derivation of ? to ?. In the same sense ?*LM is the transitive closure of ?LM.