### Context Free Grammar Question Bank

**Context Free Grammar Question Bank**

**Question List - I**

Q.1 | (a) | Do as Directed. | |

(i) Define CFG. What is Meaning of Context Free? | 2 | ||

(ii) List out steps to convert CFG in to CNF | 2 | ||

(iii) Define Inherently Ambiguous. | 1 | ||

(b) | Find out What Language is Generated by following CFG. | 5 | |

(i) S → aT | bT | Λ. T → aS | bS. | |||

(ii) S → aA | bC | b. A → aS | bB. B → aC | bA | a. C → aB | bS | |||

Q.2 | (a) | Define Derivation Tree or Parse Tree. Show that following grammar is Ambiguous and Find out Unambiguous grammar for same. S → aaaaS | aaaaaaaS | Λ. | 5 |

(b) | Prove that The Context Free Grammar G1 with Productions S1 → S1 + T | T T → T * F | F F → ( S1 ) | ais Ambiguous. | 5 | |

OR | |||

(b) | Find out CFG for L = { x є {0, 1}* | n _{0}(x) = n_{1}(x) } | 5 |

**Question List - II**

Q.1 | (a) | Do as Directed. | |

| | (i) List out Applications of CFG. | 2 |

| | (ii) Find out CFG for Regular Expression : (011 + 1)* (01)* | 2 |

| | (iii) Define Linear Grammar. | 1 |

| (b) | Find out CFG for given Language. | 5 |

| | (i) The Set of Odd-Length string in {a, b}* with middle Symbol a. | |

| | (ii) The Set of Odd-Length string in {a, b}* whose first, middle, and last Symbols are all the same. | |

Q.2 | (a) | Define Leftmost and Rightmost Derivation. Show that following grammar is Ambiguous and Find out Unambiguous grammar for same. S → A | B. A → aAb | ab. B → abB | Λ | 5 |

| (b) | Define Nullable Variable and Unit Production. Find out CFG with no Λ- Productions and no Unit Productions. S → A | B | CA → aAa | BB → bB | bbC → aCaa | DD → baD | abD |aa | 5 |

| | OR | |

| (b) | Define Regular Grammar. Find a Regular Grammar generating L – {Λ} | 5 |

**Question List - III**

Q.1 | (a) | Do as Directed. | |

| | (i) Define Balanced Strings of Parentheses. | 2 |

| | (ii) Define CFL. List out Application of CFL. | 3 |

| (b) | Find out CFG for (1) L = { a ^{i }b^{j }c^{k} | j=i or j=k }(2) L = { a ^{i }b^{j } | i < 2j } | 5 |

Q.2 | (a) | Define An Ambiguous Grammar. Show that following grammar is Ambiguous and Find out Unambiguous grammar for same. S → A → aA | Λ. B → bB | Λ | 5 |

| (b) | Let G be the Context Free Grammar with Productions S → S + S | S * S | ( S ) | aand Let G1 be the Context Free Grammar with Productions S1 → S1 + T | T T → T * F | F F → ( S1 ) | aThen L (G) = L (G1). | 5 |

| | OR | |

| (b) | Define CNF. Convert following CFG in to CNF. S → AACD.A → aAb | Λ C → aC | aD → aDa | bDb | Λ | 5 |

## Comments

## Post a Comment