CFG- Context Free Grammar

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

Zitoc

We are a team of writers, researchers, and editors who are passionate about helping others live their best lives. We believe that life is a beautiful gift. We try to live our lives to the fullest and enjoy every moment. We are always learning and growing, and we cherish the relationships we have with our family and friends.