Ambiguity and decision problems for local adjunct languages

摘要

Some of the formal properties of the local adjunct languages of Joshi, Kosaraju, and Yamada are developed. This class of languages is a proper subclass of the context-free languages and is related to the star languages. The first result is that a bounded context-free language is a local adjunct language iff it is regular. Next, many questions regarding local adjunct grammars and languages are shown to be unsolvable. In particular, it is not solvable if the local adjunct language generated by an arbitrary (local adjunct) grammar is regular. Finally, an inherently ambiguous local adjunct language (with respect to the class of local adjunct grammars) is demonstrated.