Bag Context Picture Grammars

Abstract Random context picture grammars (RCPGs) have become established as a method of syntactic picture generation. They are context-free grammars with regulated rewriting, where the application of a rule in the grammar is regulated by two sets of variables, the so-called permitting and forbidding context sets. In this paper, we introduce bag context picture grammars (BCPGs). They are also context-free grammars, but the application of a rule is regulated by a k -tuple of integers, the so-called bag, which changes during a derivation. We prove that any RCPG can be written as a BCPG and illustrate the rewriting process with several examples. We then consider one set of pictures and discuss why it is easier to write a BCPG that generates a variation on the set, and modify that BCPG again, should we wish to, than to do the same to the RCPG that generates the original picture set. This allows for application in visual password systems.