|
Intelligent systems. Theory and applications, 2019, Volume 23, Issue 4, Pages 27–38
(Mi ista247)
|
|
|
|
This article is cited in 1 scientific paper (total 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.
Citation:
A. Bernadotte, A. V. Galatenko, “Structural automaton design for solving the problem of exponential blowup for one class of regular languages”, Intelligent systems. Theory and applications, 23:4 (2019), 27–38
Linking options:
https://www.mathnet.ru/eng/ista247 https://www.mathnet.ru/eng/ista/v23/i4/p27
|
|