Search code examples
context-free-grammarautomataautomata-theory

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.

Solution

  • 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?