Bracketed context-free languages

摘要

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)⊆L(G2) and whether L(G1)∩L(G2) is empty are solvable problems for arbitrary bracketed grammars G1 and G2 with the same brackets and same terminals. Finally, bracketed languages are shown to be codes with strong properties.