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

Pattern selector grammars are defined in general. We concentrate on the study of special grammars, the pattern selectors of which contain precisely k ''one''s \((0^*(10^*)^ k)\) or k adjacent ''one''s \((0^*1^ k0^*)\). This means that precisely k symbols (resp. k 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 \(k=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 \(k=2\), are log-space reducible to the context-free languages. The membership problem is thus solvable in \(\log^ 2\) space.