Blog picture


Blog image KHUSHBOO RANI Shared publicly - Apr 15 2020 10:48PM

Context Free Grammar (MCA sem-2, MSc.(IT) -4)

Context-Free Grammars

A context-free grammar basically consists of a finite set of grammar rules. In order to define grammar rules, we assume that we have two kinds of symbols: the terminals, which are the symbols of the alphabet underlying the languages under consideration, and the nonterminals, which behave like variables ranging over strings of terminals. A rule is of the form A α, where A is a single nonterminal, and the right-hand side α is a string of terminal and/or nonterminal symbols.


A context-free grammar is a 4-tuple (V, T, P,S) where

  1. V is a finite set called the variables
  2. T is a finite set called the terminals
  3. P is a finite set of rules, called productions.
  4. S V is the start variable.


            Grammar G: ({S, A, B}, {a, b}, S, {S →AB, A →a, B →b})


S, A, and B are Non-terminal symbols;

a and b are Terminal symbols

S is the Start symbol

Productions, P : S AB, A a, B b


Post a Comment

Comments (0)