Difference between revisions of "Grammar"

From eplmediawiki
Jump to: navigation, search
Line 11: Line 11:
'''See following grammar example:''' [http://epl.di.uminho.pt/~gepl/LP/nLPDgrammar.pdf nLPD grammar]
'''See following grammar example:''' [http://eplmediawiki.di.uminho.pt/uploads/NLPDgrammar.pdf nLPD grammar]
[[Category: Basic Concepts]]
[[Category: Basic Concepts]]

Revision as of 19:39, 27 February 2013

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