RUS  ENG
Full version
JOURNALS // Intelligent systems. Theory and applications // Archive

Intelligent systems. Theory and applications, 2019 Volume 23, Issue 4, Pages 27–38 (Mi ista247)

This article is cited in 1 paper

Part 2. Special Issues in Intellectual Systems Theory

Structural automaton design for solving the problem of exponential blowup for one class of regular languages

A. Bernadotte, A. V. Galatenko


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.

Keywords: DFA, structural automaton, regular language, exponential blowup.



© Steklov Math. Inst. of RAS, 2025