A context-free grammar (CFG) is a set of recursive rewriting rules (or productions) used to generate patterns of strings.

A context-free grammar is define with the help of 4-tuple (V, T, S, P) where;

  1. V is the finite set of nonterminal symbols, which are placeholders for patterns of terminal symbols that can be generated by the nonterminal symbols. Nonterminals in CFG are also known as variables. It represents by capital letters of alphabets, for example; A, B, …. X, Y etc.
  2. T is a finite set of terminal symbols, which are the characters of the alphabet that appear in the strings generated by the grammar. It represents by small letters of alphabets (like; a, b, c, .. .. .., x, y, z), binary digits (0, 1) and digits as wells (like; 1, 2, 3, .. .. ..), for example; a, b, c, 0, 1 etc.
  3. P is a finite set of productions rules, which are the rules for replacing (or rewriting) nonterminal symbols (on the left side of the production) in a string with other nonterminal or terminal symbols (on the right side of the production). In short, “a finite set of rewriting rules called productions”.
    P ⊆ V × (V ∪ T)
    In CFG every production rule is of the form A→α, where A is a nonterminals and α is a sequence of nonterminals and terminals.
  4. S ∈ is a start symbol, which is a special nonterminal symbol that appears in the initial string generated by the grammar.

Notation of CFG:

  1. Nonterminals denoted by capital letters of alphabets, for example; A, B, …. X, Y etc.
  2. Terminals denoted by small letters of alphabets (like; a, b, c, .. .. .., x, y, z), binary digits (0, 1) and digits as wells (like; 1, 2, 3, .. .. ..), for example; a, b, c, 0, 1 etc.
  3. A string of terminals or a word w ∈ L is represented using u, v, w, x, y, z etc.
  4. A sentential form is a string of terminals and variables and it is denoted by α, β, γ etc.

Procedure to generate a string of terminal symbols from a Context Free Grammar, we can apply following steps:

  1. Begin with a string consisting of the start symbol;
  2. Apply one of the productions with the start symbol on the left hand size, replacing the start symbol with the right hand side of the production;
  3. Repeat the process of selecting nonterminal symbols in the string, and replacing them with the right hand side of some corresponding production, until all nonterminals have been replaced by terminal symbols.

Examples of Context Free Grammar:

{0n1n:n ≥ 0}{0n1n: n ≥ 0}  is context-free because it is generated by the context-free grammar ({S}, {0,1}, R,S) ({S}, {0,1}, P, S), where the set of rules, P, is as;

S→0S1ε
            (ε to denote the empty or null string.)

1 COMMENT

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.