Proving containment of bounded AFL

摘要

A study is made of necessary conditions in order for a bounded language V to be in the smallest [full] (semi-)AFL generated by a bounded language U. Two major classes of bounded languages are introduced. Specific necessary conditions are then derived for the case when U and V are both in one of these classes. For a wide variety of pairs (U, V) at least one of the necessary conditions is violated. The net result of these conditions is thus the establishment of techniques for proving that V is not in the smallest [full] (semi-)AFL generated by U. A typical example given is that the language Download : Download full-size image is not in the smallest full AFL generated by the language Download : Download full-size image.