The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Cet article présente une nouvelle méthode pour traduire une expression régulière en un automate fini non déterministe (un NFA en abrégé). Laisser r être une expression régulière et laisser M être un automate de Thompson pour r. Nous introduisons d'abord un automate de Thompson étiqueté défini en attribuant deux types d'expressions qui dénotent des préfixes et des suffixes de mots dans L(r) à chaque état de M. Nous donnons ensuite de nouveaux NFA ϵ-libres construits à partir d’un automate de Thompson étiqueté. Ces NFA sont appelés un automate d'équation de préfixe et à la un automate d'équation de suffixe. Nous montrons qu’un automate d’équation à suffixe est isomorphe à un automate d’équation défini par Antimirov. De plus, nous donnons un NFA appelé un automate d'équation unifié en rejoignant deux NFA. Ainsi, le nombre d’états d’un automate d’équation unifié peut être inférieur à celui d’un automate d’équation.
Hiroaki YAMAMOTO
Shinshu University
Hiroshi FUJIWARA
Shinshu University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Hiroaki YAMAMOTO, Hiroshi FUJIWARA, "A New Finite Automata Construction Using a Prefix and a Suffix of Regular Expressions" in IEICE TRANSACTIONS on Information,
vol. E104-D, no. 3, pp. 381-388, March 2021, doi: 10.1587/transinf.2020FCP0010.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2020FCP0010/_p
Copier
@ARTICLE{e104-d_3_381,
author={Hiroaki YAMAMOTO, Hiroshi FUJIWARA, },
journal={IEICE TRANSACTIONS on Information},
title={A New Finite Automata Construction Using a Prefix and a Suffix of Regular Expressions},
year={2021},
volume={E104-D},
number={3},
pages={381-388},
abstract={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.},
keywords={},
doi={10.1587/transinf.2020FCP0010},
ISSN={1745-1361},
month={March},}
Copier
TY - JOUR
TI - A New Finite Automata Construction Using a Prefix and a Suffix of Regular Expressions
T2 - IEICE TRANSACTIONS on Information
SP - 381
EP - 388
AU - Hiroaki YAMAMOTO
AU - Hiroshi FUJIWARA
PY - 2021
DO - 10.1587/transinf.2020FCP0010
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E104-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2021
AB - 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.
ER -