CFG- Context-Free Grammar

CFG- Context-free grammar is semantic free grammar. CFG has the following terms.

1. Terminals
2. Non Terminals
3. Production ǀ Rule

Terminals:

 By using the terminals we can terminate our language.

Non Terminal:

Through which language cannot be terminated.

Production:

We produce the language by applying the proper rule.

Tree  Representation form:

A parse tree is a binary tree that graphically represents the semantic information a string derived from a context-free grammar.

Representation Technique

• Root − Must be labeled by the start symbol.
• Vertex− Labeled by a non-terminal symbol.
• Leaves− Labeled by a terminal symbol or ε.

Z → x₁x₂ …… x_n  have the following tree representation.

Derivation approach:

There are two types of derivation approaches are used:

1. Top-Down approach.
2. Bottom-Up Approach.

Top-down Approach:

• Starts from tree root.
• Goes down to tree leaves using productions.

Bottom-up Approach:

• Starts from tree leaves.
• Proceeds upward to the root which is the starting symbol S.

Pumping Lemma