Context Free Grammar Example. CFG is semantic free grammar. CFG have the following terms.

Terminals: By using the terminals we can terminate our language.

Production ǀ Rule: Through which language cannot be terminated.

Non Terminals: 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 → x1x2 …… xn  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


CFG Properties and Applications

CFG Properties and Applications CFG- Context-free grammar is closure under: Union Concatenation Kleene Star Operation Union: Let suppose L1 and L2 are languages, they must have the finite set of…

Continue Reading CFG Properties and Applications