Scholarlink

Abstract <p>The algorithm presented in this article makes it possible to efficiently build and modify minimal deterministic finite automata for recognizing a given set of words, including when processing a large amount of information in real time. The key feature of this algorithm is the ability to add new words to the machine and its subsequent minimization on the fly. The algorithm is based on the lexicographic ordering of a set of input words and has a low computational complexity compared to traditional algorithms such as the Hopcroft algorithm or an algorithm using the construction of pairs of distinguishable states. The development of this algorithm is aimed at increasing the speed of constructing minimal deterministic finite automata and their modification for effective natural language processing and real-time web content analysis.</p>

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

Algorithm for Constructing a Minimal Deterministic Finite Automaton That Recognizes a Finite Set of Words

  • 期刊论文

  • 发表日期：

    2025年12月1日

查看全文
  • V. I. Shiyan

摘要

Abstract

The algorithm presented in this article makes it possible to efficiently build and modify minimal deterministic finite automata for recognizing a given set of words, including when processing a large amount of information in real time. The key feature of this algorithm is the ability to add new words to the machine and its subsequent minimization on the fly. The algorithm is based on the lexicographic ordering of a set of input words and has a low computational complexity compared to traditional algorithms such as the Hopcroft algorithm or an algorithm using the construction of pairs of distinguishable states. The development of this algorithm is aimed at increasing the speed of constructing minimal deterministic finite automata and their modification for effective natural language processing and real-time web content analysis.