Chapter: Artificial Intelligence
Context Free Grammar (CFG)
Context Free Grammar (CFG)
The grammar in which each production has exactly one terminal symbol in
its left handΣ,sideV,S,andP at least one symbol at the right
hand side is called context free grammar. A CFG is a four tuple where
Σ: Finite non empty set of terminals, the alphabet.
Each terminal symbol in a grammar denotes a language. The non terminals
are written in capital letters and terminals are written in small letters. Some
properties of CFG formalism are
®
Concatenation is the only string
combination operation.
®
Phrase structure is the only
syntactic relationship.
®
The terminal symbols have no
properties.
®
Non terminal symbols are atomic.
®
Most of the information encoded
in a grammar lies in the production rules.
®
Any attempt of extending the
grammar with semantics requires extra means.
®
Concatenation is not necessarily
the only way by which phrases may be combined to yield other phrases.
® Even if concatenation is the sole string operation, other syntactic relationships are being put forward.
For example we can write the followings:
Related Topics