Derivation In Automata

The deriving a string from grammar is called a derivation in Automata. The Representation of derivation in the form of a tree is called a derivation tree.

Purpose of Derivation

A derivation tree is useful when a string and grammar (production rules) are given, and we must check whether the string belongs to grammar.

Example of Derivation

The following production rules are given

  S → xB

B → xS| ε

And suppose a string W= xxx.

A derivation and its tree are possible if a given string is derived from given production rules.

Types of Derivation

There are four basic types of derivations in the theory of Automata

  • Leftmost derivation
  • Rightmost derivation
  • Parse tree 
  • Syntax tree

Derivation in Automata

 However, the first two types of derivations are mainly used.

Remember

  • Leftmost and Rightmost derivation, parse, and syntax trees will be similar for unambiguous grammars.
  • Leftmost and Rightmost derivation, parse, and syntax trees will not be similar. For ambiguous grammar,