(more info)

 Math for the people, by the people.

donor list - find out how

Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS

Advanced search

Login

create new user
name:
pass:
forget your password?

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (236)
Orphanage
Unclass'd (1)
Unproven (540)
Corrections (51)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Copyright
About

derivation tree

(Definition)

Given a formal grammar $G=(\Sigma,N,P,\sigma)$, recall that a derivation from words $u$ to $v$ over $\Sigma$ can be visualized as a finite sequence of words over , connected by the binary relation $\Rightarrow$:

$$u_0 \Rightarrow u_1 \Rightarrow \cdots \Rightarrow u_n$$ (1)

where $u=u_0$ and $v=u_n$. Each $u_i \Rightarrow u_{i+1}$ is a derivation step, which means that there is a production in $P$ which, when applied to $u_i$, yields $u_{i+1}$. In other words, there is $A\to B$ in $P$ such that $u_i=xAy$ and $u_{i+1}=xBy$, where $x,y$ are words over .

When the formal grammar $G$ is context-free, a derivation can be represented by an ordered tree, revealing the structure behind the derivation that is usually not apparent in the linear representation $(1)$ above. This ordered tree is variously known as a derivation tree or a parse tree, depending how it is being used.

In the foregoing discussion, $G$ is context-free, and any derivation of $G$ begins with $\sigma$, the starting non-terminal.

Definition. A parse tree of $G$ is an ordered tree $T$ such that

1. the nodes of $T$ are labeled by elements of , or the empty word $\lambda$,
2. if a node with label $A$ has children $N_1, \ldots, N_k$ such that $N_1 < \cdots < N_k$, and that each $N_i$ has label $A_i$, then $A \to A_1 \cdots A_k$ is a production of $P$.

A parse tree such that the root has label $\sigma$ is called a derivation tree, or a generation tree. Every subtree of a derivation tree is a parse tree.

Remark. Since $G$ is context-free, in a parse tree, any node that is not a leaf is labeled by a non-terminal symbol.

For example, if $\Sigma = \lbrace \sigma, a, b, X, Y\rbrace$, $N=\lbrace \sigma, X, Y\rbrace$, and the productions of $P$ are

$$\sigma \to aXY, \quad X\to bYb, \quad Y\to Xa, \quad Y\to a,$$

then

represents a derivation tree of $G$. The tree represents the following derivations

• $\sigma \Rightarrow aXY \Rightarrow abYbY \Rightarrow abXabY \Rightarrow abXabb$
• $\sigma \Rightarrow aXY \Rightarrow abYbY \Rightarrow abYbb \Rightarrow abXabb$
• $\sigma \Rightarrow aXY \Rightarrow aXb \Rightarrow abYbb \Rightarrow abXabb$

Definition. If $\ell_1, \ldots, \ell_m$ are the leaves of a parse tree $T$, with $\ell_1 < \cdots < \ell_m$, then the result of $T$ is the word $B_1\cdots B_m$, where $B_i\in \Sigma$ is the label of $\ell_i$. A word over is said to correspond to a parse tree if it is the result of the tree.

In the example above, the result of the tree is $abXabb$.

Remark. A derivable word may correspond to several derivation trees. See the entry ambiguous grammar for more detail.

Bibliography

1

H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, New Jersey (1981).

2

A. Salomaa, Formal Languages, Academic Press, New York (1973).

3

J.E. Hopcroft, J.D. Ullman, Formal Languages and Their Relation to Automata, Addison-Wesley, (1969).

"derivation tree" is owned by CWoo.

(view preamble | get metadata)

View style: jsMath HTMLHTML with imagespage imagesTeX source

Other names:

generation tree

Also defines:

parse tree, result of a derivation tree

This object's parent.

Attachments:

derivation tree of a derivation (Definition) by CWoo

Log in to rate this entry.
(view current ratings)

Cross-references: ambiguous grammar, derivable, tree, represents, leaf, root, children, label, empty word, elements, nodes, non-terminal, representation, structure, ordered tree, context-free, production, binary relation, connected, finite sequence, derivation, formal grammar
There are 4 references to this entry.

This is version 7 of derivation tree, born on 2009-08-23, modified 2009-08-24.
Object id is 11873, canonical name is DerivationTree.
Accessed 472 times total.

Classification:

AMS MSC:	68Q45 (Computer science :: Theory of computing :: Formal languages and automata)
	68Q42 (Computer science :: Theory of computing :: Grammars and rewriting systems)

Pending Errata and Addenda

None.

Discussion

Style: FlatThreaded Expand: allnone123456789 Order: Oldest FirstNewest first

forum policy

No messages.

Interact

post | correct | update request | add derivation | add example | add (any)