Abstract:
It is well known that recognition of a language specified by a regular expression of the form $\bigcup_{i=1}^{n}.*\alpha_i.*\beta_i.*$, where $\alpha_i, \beta_i$ are words over some alphabet, in the general case requires a deterministic automaton with the number of states which is exponential in $n$. We propose a design of a structural automaton of a polynomial spatial complexity that recognizes languages from a given class.