Context Free Grammar CFG in theory of automata

What is Context Free Grammar CFG?

CFG is a set of rules for automating the machine and generating the strings of a language. CFG generates a pattern of strings.

CFG has following parts;

  • Start symbol
  • Set of terminal symbols
  • Set of non-terminal symbols
  • Set of rules

What are methods for derivation of trees?

There are two techniques;

  1. Bottom-up approach
  2. Top-down approach

What is Bottom-up Approach? 

Firstly, Starts with leaves of the tree.

Move upward to the starting symbol.

What is Top-down Approach?

Starts with starting symbol.

Move down to the tree leaves.

Give an example of CFG?

Built the CFG for the language of all those strings having 0 a’s or many a’s?

S ⇒ aS | ε

Now we can read multiple a’s from this CFG.

For example;

To read o a’s from S ⇒ aS | ε

S ⇒ aS | ε

S⇒ ε


To read 1 a from S ⇒ aS | ε

S ⇒ aS

S⇒ a ε

S⇒ a 


To read 2 a from S ⇒ aS | ε

S ⇒ aS

S ⇒ aaS

S⇒ a ε

S⇒ a 

and similarly, we can read many a’s from this CFG.

Fazal Rehman Shamil
Welcome to all friends. The reason for our success is only your love for T4Tutorials. Our team is always available to answer your queries regarding any kind of confusions or discussion regarding your study and career matters. For discussion with us please join our facebook group "". The link of the group is mentioned below. Thanks and love to all for connecting with us. We are nothing without you. Love you all.....

Leave a Reply