PRINCIPAL AFL,
Abstract
A (full) principal AFL is a (full) AFL generated by a single language, i.e., it is the smallest (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, a representation theorem for each language in a (full) principal AFL is given involving the generator and one application each of concatenation, star, intersection with a regular set, inverse homomorphism, and a special type of homomorphism. Finally, it is shown that if l1 and l2 are (full) principal AFL, then so are (a) the smallest (full) AFL containing ((the intersection of L1 and L2)/L1 in l1, 12 in 12) and (b) the family obtained by substituting epsilon-free languages of 12 into languages of l1. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 12, 1970
- Accession Number
- AD0702527
Entities
People
- Seymour Ginsburg
- Sheila Greibach
Organizations
- System Development Corporation