Types of Derivation Tree:

There are three types of Derivation trees;

  • Leftmost Derivation tree
  • Rightmost derivation tree
  • Mixed derivation tree

Leftmost derivation: A leftmost derivation is obtained by applying production to the leftmost variable in each successive step.

Example:

Consider the grammar G with production:

S → aSS          (Rule: 1)
A → b             (Rule: 2)

Compute the string w = ‘aababbb’ with left most derivation.
S   ⇒ aSS             (Rule: 1)
⇒ aaSSS         (Rule: 1)
⇒ aabSS          (Rule: 2)
⇒ aabaSSS      (Rule: 1)
⇒ aababSS      (Rule: 2)
⇒ aababbS      (Rule: 2)
⇒ aababbb      (Rule: 2)

To obtain the string ‘w’ the sequence followed is “left most derivation”, following “1121222”.

Rightmost derivation: A rightmost derivation is obtained by applying production to the rightmost variable in each step.

Example:

Consider the grammar G with production:

S → aSS          (Rule: 1)
A → b             (Rule: 2)

Compute the string w = ‘aababbb’ with right most derivation.

        S ⇒ aSS             (Rule: 1)
⇒ aSb              (Rule: 2)
⇒ aaSSb          (Rule: 1)
⇒ aaSaSSb      (Rule: 1)
⇒ aaSaSbb      (Rule: 2)
⇒ aaSabbb      (Rule: 2)
⇒ aababbb      (Rule: 2)

To obtain the string ‘w’ the sequence followed is “right most derivation”, following “1211222”.

Mixed Derivation: In a mixed derivation the string is obtained by applying production to the leftmost variable and rightmost variable simultaneously as per the requirement in each successive step.

        S ⇒ aSS             (Rule: 1)
⇒ aSb              (Rule: 2)
⇒ aaSSb          (Rule: 1)
⇒ aabSb          (Rule: 2)
⇒ aabaSSb      (Rule: 1)
⇒ aabaSbb      (Rule: 2)
⇒ aababbb      (Rule: 2)

To obtain the string ‘w’ the sequence followed is “mixed derivation”, following “1212122”.

Example 1: A grammar G which is context-free has the productions

S → aAB        (Rule: 1)
A → Bba         (Rule: 2)
B → bB           (Rule: 3)
B → c              (Rule: 4)

Compute the string w = ‘acbabc’ with left most derivation.

        S ⇒ aAB                        (Rule: 1)
⇒ aBbaB         (Rule: 2)
⇒ acbaB          (Rule: 4)
⇒ acbabB        (Rule: 3)
⇒ acbabc         (Rule: 4)
Left most derivation Tree to obtain the string ‘w’ as follows;

Derivation Tree solved example
Derivation Tree solved example

Example 2: A grammar G which is context-free has the productions

S → a              (Rule: 1)
S → aAS         (Rule: 2)
A → bS           (Rule: 3)

Compute the string w = ‘abaabaa’ with left most derivation.

        S ⇒ aAS             (Rule: 2)
⇒ abS              (Rule: 3)
⇒ abaAS         (Rule: 1)
⇒ abaabSS      (Rule: 2)
⇒ abaabaS      (Rule: 3)
⇒ abaabaa       (Rule: 3)

Left most derivation Tree to obtain the string ‘w’ as follows;

Derivation Tree solved example
Derivation Tree solved example

Example 3: A grammar G = (N, T, P, S) with N = {E}, S = E, T = {id, +, *, c}

E → E + E        (Rule: 1)
E → E * E        (Rule: 2)
E → ( E )         (Rule: 3)
E → id             (Rule: 4)

Obtain the derivation tree of expressions:
(i)         id * id + id
(ii)        id + id * id

Solution:

(i)

E ⇒ E + E                   (Rule: 1)
⇒ E * E + E            (Rule: 2 and left derivation)
⇒ id * id + id          (Rule: 4 and left derivation)

Derivation Tree solved example 3.1
Derivation Tree solved example 3.1

(ii)

E ⇒ E * E                    (Rule: 2)
⇒ ( E ) * E              (Rule: 3 and left derivation)
⇒ ( E + E ) * E        (Rule: 1 and left derivation)
⇒ ( id + id ) * id      (Rule: 4)

Derivation Tree solved example 3.2
Derivation Tree solved example 3.2

Example 4: A grammar G = (N, T, P, S) with N = {S, A}, T = {a, b} and P are as follow;

S → aS            (Rule: 1)
S → aA            (Rule: 2)
A → bA            (Rule: 3)
A → b              (Rule: 4)

Obtain the derivation tree and L(G).

Solution:

(i)         S ⇒ aA            (Rule: 2)
⇒ ab             (Rule: 4)

(ii)        S ⇒ aS             (Rule: 1)
⇒ aaA            (Rule: 3)
⇒ aab                        (Rule: 4)

(iii)       S ⇒ aS             (Rule: 1)
⇒ aaS            (Rule: 1)
⇒ aaaA          (Rule: 3)
⇒ aaab           (Rule: 4)

(iv)       S ⇒ aS             (Rule: 1)
⇒ aaS            (Rule: 1)
⇒ aabA          (Rule: 3)
⇒ aabb           (Rule: 4)

(v)        S ⇒ aS             (Rule: 1)
⇒ aaS            (Rule: 1)
⇒ aaaS           (Rule: 1)
⇒ aaaaA         (Rule: 3)
⇒ aaaab         (Rule: 4)

Hence; Language generated by the above grammar L(G) = { ab, aab, aaab, aabb, aaaab, .. .. .. ..}

By analyzing the above generated string form the grammar G, there has a similar pattern in all computed strings, i.e.

  • The minimum length of the string consist ab always which means occurrence of a’s = 1, and b’s = 1 as well.
  • In the generated strings a’s followed by b’s always that means strings are always start with a’s and end with b’s.
  • There is no limitation of number of occurrence of a’s and b’s and no relation of repetition of a’s and b’s.

Thus we can write the language of the grammar L(G) = {an bm : n > 0 ; m > 0}

And the derivation tree of the grammar G is:

Derivation Tree solved example 4
Derivation Tree solved example 4

LEAVE A REPLY

Please enter your comment!
Please enter your name here