Pattern selector grammars and several parsing algorithms in the context-free style

AbstractPattern selector grammars are defined in general. We concentrate on the study of special grammars, the pattern selectors of which contain precisely κ “one”s (0∗(10∗)κ) or κ adjacent “one”s (0∗1κ0∗). This means that precisely κ symbols (resp. κ adjacent symbols) in each sentential form are rewritten. The main results concern parsing algorithms and the complexity of the membership problem. We first obtain a polynomial bound on the shortest derivation and hence an NP time bound for parsing. In the case κ = 2, we generalize the well-known context-free dynamic programming type algorithms, which run in polynomial time. It is shown that the generated languages, for κ = 2, are log-space reducible to the context-free languages. The membership problem is thus solvable in log2 space