关键词: 二元文法 袋自动机 袋语言 推导

Abstract:

The concept of binary grammar is presented, and it is shown that the languages accepted by bag automata are exactly the languages generated by binary grammar. The concepts of balanced derivations, increasing derivations, decreasing derivations and transitive derivations are defined. A set of necessary and sufficient conditions for determining a bag language to be a regular language, a context-free language or a context-sensitive language are given.

Key words: binary grammar, bag automata, bag language, derivation