2024-03-28T10:25:08Z
https://soar-ir.repo.nii.ac.jp/oai
oai:soar-ir.repo.nii.ac.jp:02001210
2022-12-14T04:15:31Z
1221:1222
A New Finite Automata Construction Using a Prefix and a Suffix of Regular Expressions
Yamamoto, Hiroaki
Fujiwara, Hiroshi
regular expression
nondeterministic finite automaton
This paper presents a new method to translate a regular expression into a nondeterministic finite automaton (an NFA for short). Let r be a regular expression and let M be a Thompson automaton for r. We first introduce a labeled Thompson automaton defined by assigning two types of expressions which denote prefixes and suffixes of words in L(r) to each state of M. Then we give new ϵ-free NFAs constructed from a labeled Thompson automaton. These NFAs are called a prefix equation automaton and a suffix equation automaton. We show that a suffix equation automaton is isomorphic to an equation automaton defined by Antimirov. Furthermore we give an NFA called a unified equation automaton by joining two NFAs. Thus the number of states of a unified equation automaton can be smaller than that of an equation automaton.
Article
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS E104D(3) : 381-388(2021)
journal article
2021-03-01
application/pdf
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
3
E104D
381
388
1745-1361
AA10826272
https://soar-ir.repo.nii.ac.jp/record/2001210/files/16K00033_1.pdf
eng
10.1587/transinf.2020FCP0010
https://doi.org/10.1587/transinf.2020FCP0010
© 2021 The Institute of Electronics, Information and Communication Engineers