CFG- Context Free Grammar

  • Post author:
Download PDF
Advertisement

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 ε.
    Advertisement

Z → x1x2 …… xhave the following tree representation.

CFG- context free grammar

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.

Top-down Approach

Bottom-up Approach:

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

Bottom-up ApproachPumping Lemma

Advertisement