A new automata for parsing semi-bracketed contextual grammars

Bracketed and fully bracketed contextual grammars were introduced to bring the concept of tree structure to the strings by associating a pair of parentheses to the adjoined contexts in the derivation. But these grammars fail to generate the basic non-context free languages thus unable to provide a syntactical representation to natural languages. To overcome this problem, a new variant called semi-bracketed contextual grammar was introduced recently, where the selectors can also be non-minimally Dyck covered strings. The membership problem for the new variant is left unsolved. In this paper, we propose a parsing algorithm (for non-projected strings) of maximal semi-bracketed contextual grammars. In this process, we introduce a new automaton called k-queue Self Modifying Weighted Automata (k-quSMWA).