# 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 = {a

^{k}b

^{l}c

^{k}}∪{a

^{m}b

^{m}c

^{n}} 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.

*: Every CFG production of the CNF grammar contains either two non terminals or a single terminal in the RHS of the production.*

**Chomsky Normal Form**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.

*: Every CFG production of CNF grammar contains a single terminal (T ) followed by any sequence of non-terminals(V*).*

**Greibach normal form**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