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…
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.
- 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
- Top-Down approach
- 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