BRACKETED CONTEXT FREE LANGUAGES.
Abstract
A bracketed grammar is a context free grammar in which indexed brackets are inserted around the right-hand sides of the rules. The language generated by a bracketed grammar is a bracketed language. An algebraic condition is given for one bracketed language to be a subset of another. The intersection and the difference of two bracketed languages with the same brackets and terminals are context free (although not necessarily bracketed) languages. Whether L(G1) is a subset of L(G2) and whether the intersection of L(G1) with L(G2) is empty are solvable problems for arbitrary bracketed grammars G1 and G2 with the same brackets and same terminals. Bracketed languages are shown to be codes with strong properties. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 04, 1966
- Accession Number
- AD0631337
Entities
People
- Michael A. Harrison
- Seymour Ginsburg
Organizations
- System Development Corporation