Ogden's lemma for random permitting and forbidding context picture languages and table-driven context-free picture languages
Date
2015-05-06
Authors
Idahosa, Joy O
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Random context picture grammars are used to generate pictures through successive refinement.
There are three important subclasses of random context picture grammars, namely random permitting
context picture grammars, random forbidding context picture grammars and table-driven
context-free picture grammars. These grammars generate the random permitting context picture
languages, random forbidding context picture languages and table-driven context-free picture
languages, respectively. Theorems exist which provide necessary conditions that have to be
satisfied by a language before it can be classified under a particular subclass. Some of these
theorems include the pumping and shrinking lemmas, which have been developed for random
permitting context picture languages and random forbidding context picture languages respectively.
Two characterization theorems were developed for the table-driven context-free picture
languages.
This dissertation examines these existing theorems for picture languages, i.e., the pumping
and shrinking lemmas and the two characterisation theorems, and attempts to prove theorems,
which will provide an alternative to the existing theorems and thus provide new tools for identifying
languages that do not belong to the various classes. This will be done by adapting Ogden’s
idea of marking parts of a word which was done for the string case. Our theorems essentially involve
marking parts of a picture such that the pumping operation increases the number of marked
symbols and the shrinking operation reduces it.
Description
A dissertation submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in fulfilment of requirements for the degree of Master of Science. Johannesburg, February 16, 2015.