Thoery of computaion(b.TECH 4TH sEM)
Unit-2 Context-Free Grammar 1. Context Free Grammar is formal grammar, the syntax or structure of a formal language can be described using context-free grammar (CFG). 2. G is context free if every production is of the form A->α, where A ∊ Vn and α ∊ (Vn ∪ T)*. 3. The grammar has four tuples: G = (Vn, T, P, S). V - It is the collection of variables or nonterminal symbols. It is denoted by capital letters T - It is a set of terminals. It is denoted by lower case letters. P - It is the production rules that consist of both terminals and nonterminal. S - It is the Starting symbol. 4. left-hand side of the G, here in the example can only be a Variable, it cannot be a terminal or variable in only capital letter. 5. But on the right-hand side here it can be a Variable or Terminal or both combination of Variable and Terminal. 6. Example the grammar A = { S, a,b, P,S} having production : · Here S is the starti