Oops! It appears that you have disabled your Javascript. In order for you to see this page as it is meant to appear, we ask that you please re-enable your Javascript!

Context Free Grammar CFG in theory of automata

Last modified on May 26th, 2018 at 1:48 pm

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.

Prof. Fazal Rehman Shamil
Researcher, Publisher of International Journal Of Software Technology & Science ISSN: 2616-5325
Instructor, SEO Expert, Web Programmer and poet.
Feel free to contact.