Grammars and Automata

Perspective on Grammars

We are interested in the derivation trees generated by CFGs rather than just the strings those trees yield. Consequently, we view the grammars as licensing trees rather than rewriting strings. Under the string-rewriting perspective, a grammar operates by taking strings and rewriting them to form new strings. For example, the grammar G might rewrite the string A as follows:

A -> BC -> AAC -> AACC

In this example, the operation of G first replaces the A with BC; next it replaces the newly-formed B with AA; and finally it replaces the C with CC.

In contrast, our perspective on grammars operates by taking trees and extending them by hanging purely local trees at the leaves. A local tree consists of a root with optional children but no grandchildren. The following are all examples of local trees:

  A        B        C      A      W      S
 / \      / \      / \     |     /|\
B   C    A   A    C   C    B    X Y Z

while these are not:

    A          X
   / \         |
  B   C        Y
 / \           |
D   E          Z

From the local tree perspective, our example derivation would look like this:

                      A              A
         A           / \           /   \
A  ->   / \   ->    B   C  ->    B       C
       B   C       / \          / \     / \
                  A   A        A   A   C   C

In the tree we have just constructed, the local trees used are those from the first three local tree examples. Initially the first example local tree, rooted in A, is hung from the leaf (and root) A; next the second example local tree, rooted in B is hung from the leaf B; and finally the third example local tree, rooted in C is hung from the leaf C. If we read off the leaves of the tree, or the yield, at each step, we find that they match the string from the equivalent step in the string-rewriting mechanism. Thus the local tree perspective consists of building trees up by hanging local trees on the leaves; the final yield presents the constructed string; and the structure of the tree gives exactly how the string was constructed.

Stemming from this view, we formalize a grammar G as the set of local trees used in the grammar. Further, we define G(S), where S is some set of start symbols, to be the derivation forest licensed by G when starting from any of the symbols in S; this is the set of all trees such that every node in the tree is the root of some local tree in G. In particular, this means that the leaves of the tree must be the roots of local trees in G that have no children. This requirement gives us a sense of what symbols correspond to the terminals and the non-terminals of a grammar in the string-rewriting perspective; the non-terminals are the symbols that are the roots of local trees with children, and the terminals are the symbols that are the roots of local trees without children. As a generalization, we do not require these two sets to be distinct.

Looking for something that's not here? Contact:

Last updated: Monday, 26-Jul-2004 14:22:53 EST
#1138

Grammars andAutomata

Grammars and Automata

Perspective on Grammars

Grammars and
Automata