Context Free Grammar ( CFG )
CONTEXT FREE GRAMMAR ( CFG )
Derivation of a String:
(i) Left Most Derivation (LMD) : In each sentential form , the left most non-terminal is substituted with its productions to derive a string.
(ii) Right Most Derivation (RMD) : In each sentential form , the right most non-terminal is substituted with its productions to derive a string.
(iii) Parse tree : Every intermediate node of a parse tree is a non-terminal which is represented by a circle and all leaf nodes are terminal symbols.
Umambigous Grammar: The grammar is called as unambiguous grammar if every string generated from the grammar has exactly one parse tree.
# parse tree's = # LMD's = # RMD's = 1
Ambiguous grammar : The grammar is called as ambiguous grammar if there exists a string which is derived the grammar with more than one parse tree.
( # parse tree's = # LMD's = #RMD's ) > 1
Inherently Ambiguous Context Free language : For a given language if there is no equivalent .unambiguous CFG then such language is called as inherently ambiguous context free language.
L = {akblck}∪{ambmcn} is an example of an inherently ambiguous CFL.
Reduced CFG ( non-redundant CFG ) : Reduced CFG is a CFG without any useless symbols.
Simplified CFG : Simplified CFG is a CFG without any null-productions,unit-productions and useless symbols.
The following order applied over a given CFG to Convert into simplified CFG.
(i) Null-productions elimination.
(ii) Unit-productions elimination.
(iii) Useless symbols elimination.
Normal forms for CFG
Types of CFG Normal forms:
1. Chomsky Normal Form: Every CFG production of the CNF grammar contains either two non terminals or a single terminal in the RHS of the production.
A -------------> BC
A --------------> a
CNF is also called binary standard form (the parse tree in CNF is always a binary tree).
(i) The number of steps required in derivation of an x-length string from the given CNF - context free grammar is : (2x - 1)
(ii) Let G be the given CNF without '∈' and unit productions and let 'k' be the maximum number of symbols on the right hand side of any production,then the equivalent CNF contain a maximum of:
( K - 1 ) |P| + |T| productions. Where, |P| = the number of productions in 'G' |T| = the number of terminals, K = maximum number of symbols on right hand side.
(iii) For the generation of 'l' length yield , the minimum height of the derivation of tree for the given CNF context free grammar is [log2l] + 1 and maximum height will be l.
2. Greibach normal form : Every CFG production of CNF grammar contains a single terminal (T ) followed by any sequence of non-terminals(V*).
V------>TV*
(i) In GNF context free grammar , the restrictions only on the positions,but not on length of right side of a production. A--->aα , Where α∈ V.
(ii) The number of steps required in derivation of an x-length string from the given GNF - Context free grammar is : x.
Derivation of a String:
(i) Left Most Derivation (LMD) : In each sentential form , the left most non-terminal is substituted with its productions to derive a string.
(ii) Right Most Derivation (RMD) : In each sentential form , the right most non-terminal is substituted with its productions to derive a string.
(iii) Parse tree : Every intermediate node of a parse tree is a non-terminal which is represented by a circle and all leaf nodes are terminal symbols.
Umambigous Grammar: The grammar is called as unambiguous grammar if every string generated from the grammar has exactly one parse tree.
# parse tree's = # LMD's = # RMD's = 1
Ambiguous grammar : The grammar is called as ambiguous grammar if there exists a string which is derived the grammar with more than one parse tree.
( # parse tree's = # LMD's = #RMD's ) > 1
Inherently Ambiguous Context Free language : For a given language if there is no equivalent .unambiguous CFG then such language is called as inherently ambiguous context free language.
L = {akblck}∪{ambmcn} is an example of an inherently ambiguous CFL.
Reduced CFG ( non-redundant CFG ) : Reduced CFG is a CFG without any useless symbols.
Simplified CFG : Simplified CFG is a CFG without any null-productions,unit-productions and useless symbols.
The following order applied over a given CFG to Convert into simplified CFG.
(i) Null-productions elimination.
(ii) Unit-productions elimination.
(iii) Useless symbols elimination.
Normal forms for CFG
Types of CFG Normal forms:
1. Chomsky Normal Form: Every CFG production of the CNF grammar contains either two non terminals or a single terminal in the RHS of the production.
A -------------> BC
A --------------> a
CNF is also called binary standard form (the parse tree in CNF is always a binary tree).
(i) The number of steps required in derivation of an x-length string from the given CNF - context free grammar is : (2x - 1)
(ii) Let G be the given CNF without '∈' and unit productions and let 'k' be the maximum number of symbols on the right hand side of any production,then the equivalent CNF contain a maximum of:
( K - 1 ) |P| + |T| productions. Where, |P| = the number of productions in 'G' |T| = the number of terminals, K = maximum number of symbols on right hand side.
(iii) For the generation of 'l' length yield , the minimum height of the derivation of tree for the given CNF context free grammar is [log2l] + 1 and maximum height will be l.
2. Greibach normal form : Every CFG production of CNF grammar contains a single terminal (T ) followed by any sequence of non-terminals(V*).
V------>TV*
(i) In GNF context free grammar , the restrictions only on the positions,but not on length of right side of a production. A--->aα , Where α∈ V.
(ii) The number of steps required in derivation of an x-length string from the given GNF - Context free grammar is : x.
No comments