Principal AFL

摘要

A (full) principal AFL is a (full) AFL generated by a single language, i.e., it is thesmallest (full) AFL containing the given language. In the present paper, a study is made of such AFL. First, an AFA (abstract family of acceptors) characterization of (full) principal AFL is given. From this result, many well-known families of AFL can be shown to be (full) principal AFL. Next, two representation theorems for each language in a (full) principal AFL are given. The first involves the generator and one application each of concatenation, star, intersection with a regular set, inverse homomorphism, and a special type of homomorphism. The second involves an a-transducer, the generator, and one application of concatenation and star. Finally, it is shown that if ℒ1 and ℒ2 are (full) principal AFL, then so are (a) the smallest (full) AFL containing {L1∩L2/L1 in ℒ1, L2 in ℒ2 and (b) the family obtained by substituting ε-free languages of ℒ2 into languages of ℒ1.