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.