Scholarlink

This paper establishes a lower bound on the number of states necessary in the worst case to simulate an n-state two-way nondeterministic finite automaton (2NFA) by a one-way unambiguous finite automaton (UFA). It is proved that for every n, there is a language recognized by an n-state 2NFA that requires a UFA with at least \(\sum _{k=1}^{n} (k - 1)! k! \left\{ \begin{array}{c}n\\ k \end{array}\right\} \left\{ \begin{array}{c}n+1\\ k \end{array}\right\} \) = \(\varOmega \big ( n^{2n+2} / e^{2n} \big )\) states, where \(\left\{ \begin{array}{c}n\\ k \end{array}\right\} \) denotes Stirling’s numbers of the second kind. This result is proved by estimating the rank of a certain matrix, which describes every possible behaviour of n-state 2NFAs during their computation.

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

On the Transformation of Two-Way Nondeterministic Finite Automata to Unambiguous Finite Automata

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Semyon Petrov,
  • Alexander Okhotin

摘要

This paper establishes a lower bound on the number of states necessary in the worst case to simulate an n-state two-way nondeterministic finite automaton (2NFA) by a one-way unambiguous finite automaton (UFA). It is proved that for every n, there is a language recognized by an n-state 2NFA that requires a UFA with at least \(\sum _{k=1}^{n} (k - 1)! k! \left\{ \begin{array}{c}n\\ k \end{array}\right\} \left\{ \begin{array}{c}n+1\\ k \end{array}\right\} \) = \(\varOmega \big ( n^{2n+2} / e^{2n} \big )\) states, where \(\left\{ \begin{array}{c}n\\ k \end{array}\right\} \) denotes Stirling’s numbers of the second kind. This result is proved by estimating the rank of a certain matrix, which describes every possible behaviour of n-state 2NFAs during their computation.