**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__

__Types of Derivation__

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

- Leftmost derivation
- Rightmost derivation
- Parse tree
- Syntax tree

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

__Remember__

__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,