CODEWITHSUNDEEP
context-free-grammarautomataautomata-theory
CSRivan
CSRivan

Reputation: 23

What is the relationship between derivation and derivation trees?

It was written in ullmans book but i did not under stand well how it works. Can anybody explain even in simple context? I'd be really glad.

Upvotes: 2

Views: 3159

Answers (1)

Josh Lee
Josh Lee

Reputation: 177624

A derivation is some sequence that starts with the start symbol S, ends with a string in the language, and the intermediate steps may contain terminals and nonterminals. Each step in the sequence expands one nonterminal using a production rule.

A parse tree is rooted at the start symbol, has terminal symbols as leaves, and the children of a node correspond to a production rule.

For instance, with the grammar S -> a | 1 | S + S, a derivation for a + a + 1 might be

S -> S + S -> a + S -> a + S + S -> a + S + 1 -> a + a + 1

and the corresponding parse tree might be

   S
 / | \
S  +  S
|    /|\
a   S + S
    |   |
    a   1

Some questions to ask at this point are: For a given language or grammar, does a particular string have only one parse tree? Only one derivation? For a particular derivation, is there a unique parse tree, or vice versa?

Upvotes: 1

Related Questions