It is proved that every regular expression of alphabetic width n, that is, with n occurrences of symbols of the alphabet, can be transformed into a deterministic finite automaton (DFA) with at most \(2^{\frac{n}{2}+(\frac{\log _2 e}{2\sqrt{2}}+o(1))\sqrt{n\ln n}}\) states recognizing the same language (the best upper bound up to date is \(2^n\) ). At the same time, it is also shown that this bound is close to optimal, namely, that there exist regular expressions of alphabetic width n over a two-symbol alphabet, such that every DFA for the same language has at least \(2^{\frac{n}{2}+(\sqrt{2} + o(1))\sqrt{\frac{n}{\ln n}}}\) states (the previously known lower bound is \(\frac{5}{4}2^{\frac{n}{2}}\) ). The same bounds are obtained for an intermediate problem of determinizing nondetermistic finite automata (NFA) with each state having all incoming transitions by the same symbol.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

From Regular Expressions to Deterministic Finite Automata: \(2^{\frac{n}{2}+\sqrt{n}(\log n)^{\varTheta (1)}}\) States Are Necessary and Sufficient

  • Olga Martynova,
  • Alexander Okhotin

摘要

It is proved that every regular expression of alphabetic width n, that is, with n occurrences of symbols of the alphabet, can be transformed into a deterministic finite automaton (DFA) with at most \(2^{\frac{n}{2}+(\frac{\log _2 e}{2\sqrt{2}}+o(1))\sqrt{n\ln n}}\) states recognizing the same language (the best upper bound up to date is \(2^n\) ). At the same time, it is also shown that this bound is close to optimal, namely, that there exist regular expressions of alphabetic width n over a two-symbol alphabet, such that every DFA for the same language has at least \(2^{\frac{n}{2}+(\sqrt{2} + o(1))\sqrt{\frac{n}{\ln n}}}\) states (the previously known lower bound is \(\frac{5}{4}2^{\frac{n}{2}}\) ). The same bounds are obtained for an intermediate problem of determinizing nondetermistic finite automata (NFA) with each state having all incoming transitions by the same symbol.