From eplmediawiki
This is the approved revision of this page; it is not the most recent. View the most recent revision.
Jump to: navigation, search

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

Personal tools