Derivations Trees:

Definition: Given a context-free grammar G  = (V, Σ, P, S), for any A  ∈ N , an A-derivation tree for G is a (V ∪ { })-tree t (a tree with set of labels (V ∪ { })) such that:

(1) t( )= A;

(2) For each nonleaf node u ∈ dom(t), if u₁,..., u_k  are successors of u, then either there is a production B  → X₁ ··· X_k in P  such that t(u) = B  and t(ui) = X_i for all i, 1 ≤ i ≤ k, or B → ∈ P , t(u)= B  and t(u1) = .A complete derivation is an S-tree whose yield belongs to Σ*.

A derivation tree for grammar

G₃  = ({E, T , F, +, ∗, (, ), a}, {+, ∗, (, ), a}, P, E),

here P is the set of rules

E → E + T, 

E → T, 

T → T ∗ F,

T → F,

F → (E),

F → a,

is shown in Figure drawn below The yield of the derivation tree is a + a ∗ a.

Figure : A complete derivation  tree

Derivations trees are related to derivations inductively as follows.

Definition: Given a context-free grammar G = (V, Σ, P, S), for A ∈ N , if π : A α is a derivation in G, we construct an A-derivation tree t_π with yield α as stated below.

(1) If n = 0, then t_π is 1-node tree such that dom(t_π)= { } and tπ (∈)= A.

(2) If A  λBρ  ⇒ λγρ = α, then if t₁ is A-derivation tree with yieldA  λBρ  associated A with the derivation A  =n-1 λBρ, and if t2 is tree associated with production B → γ (that is, if γ = X₁ ··· X_k , 

where u is the address of leaf labeled B  in t₁ .

The tree t_n is A-derivation tree associated with derivation  A α.

Given the grammar

G₂ = ({E, +, ∗, (, ), a}, {+, ∗, (,), a}, P, E),

here P is set of rules

E → E + E,

E → E ∗ E,

E -→ (E),

E → a,

the parse trees associated with 2 derivations of string a + a ∗ a are shown in Figure given below:

Figure :Two derivation trees for a + a ∗ a

The following lemma is shown easily.

Lemma: Let G = (V, Σ, P, S) be a context-free grammar. For any derivation A  α, there is a unique A-derivation tree associated with the derivation,  with yield α.  On the other hand, for any A-derivation  tree t with yield α, there is a unique leftmost derivationA α in G having t as its associated derivation tree.

Email based Automata assignment help – homework help

The study of automata is an important area of theory of computation. Students feel trouble in solving automata questions. We at www.expertsmind.com offers Automata assignment help – Automata homework help and online tutoring with best qualified and experienced computer science tutor’s help. We cover all topics including Derivations Trees in assignment help – homework help service. Get solved problems in automata theory with step by step answers anytime from expert tutors at expertsmind.