MPhil Thesis Defence


"A Survey of Greibach Normal Form: Transformation & Analysis"

By

Mr. Man Chi Ho


Abstract

Context-free grammar transformations have been explored over the past 30
years or so - before the birth of the first personal computer! The idea of
such transformations is, in general, to modify a given grammar according
to a specific transformation method. We require that such transformation
methods preserve the language of the original grammar. Thus, if G is the
original grammar, and H is a transformed version of G, then we require
that L(G) = L(H). Some example transformations on context-free grammars
are Chomsky Normal Form, Greibach Normal Form, Double Greibach Normal
Form, Extended Greibach Normal Form, to name a few. Even with the same
normal form, different researchers have suggested different algorithms
that have different focuses, including simplicity, efficiency, grammar
size, and more. The purpose of this thesis is to analyze the logic behind
different algorithms for Greibach Normal Form transformation, and how
their performance varies. We developed a Java program to implement most of
these algorithms and test for any undiscovered problems when running them
with restricted memory and processing power, as well as to serve as a
starting point for developing a full grammar transformation package. We
also study the transformation algorithms applied to extended context-free
grammars and investigate how they can be compared and related to those
used for context-free grammars.


Date:				Friday, 24 March 2006

Time:				2:30p.m.-4:30p.m.

Venue:				Room 2302
				Lifts 17-18

Committee Members:		Prof. Derick Wood (Supervisor)
				Dr. Sunil Arya (Chairperson)
				Dr. Mordecai Golin


**** ALL are Welcome ****