Bsc CSIT Semester 4 – Theory of Computation – Unit IV: Context Free Grammar (9 Hrs.)

Define Chomsky Normal Form and Greibach Normal Form in reference to CFG. Give a suitable example of each.

Explain about the Chomsky’s Hierarchy about the language and programs.

Construct the following grammer into Chomsky Normal Form.

S → abSb | a | aAb

A → bS | aAAb | ε

Given the following expression grammar for simple arithematic expression with operator + and *. E→ E+T | T T → T+F | F F → (E) | a Remove the left recursion from this grammar then simplify and convert to CNF

Define the term: Parse Tree, left-most and right-most derivation, sentential form and ambiguity with example.

Define regular grammar. Also explain the method of converting right linear grammar into equivalent finite automata.

Define context free grammar with an example. Explain with example, how context free grammar is converted to Chomsky Normal Form.

What is the meaning of the term “Context Free” in context free grammar? Justify with a suitable example. What is the need of a parse tree?

Define CFG. Construct a CFG that generates the language of all palindromes over {a,b} that do not contain the substring aa. Show the leftmost derevation and construct the equivalent parse tree for string babbbab.

Prove that the language $L=\{\,a^n b^n c^n \mid n \ge 0\,\}$ is not a context free grammar.

Define the language of a grammar. For the grammar S → 0S0 | 1 | ε, show the leftmost derivation for the string 00100 with its parse tree.

Convert the following grammar to CNF. S → AAB, A → aA | ε, B → ab | a