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
Este artigo apresenta um novo método para traduzir uma expressão regular em um autômato finito não determinístico (abreviadamente um NFA). Deixar r seja uma expressão regular e deixe M ser um autômato Thompson para r. Primeiro introduzimos um autômato de Thompson rotulado, definido pela atribuição de dois tipos de expressões que denotam prefixos e sufixos de palavras em L(r) para cada estado de M. Em seguida, damos novos NFAs livres de ϵ construídos a partir de um autômato de Thompson rotulado. Esses NFAs são chamados um autômato de equação de prefixo e um autômato de equação de sufixo. Mostramos que um autômato de equação sufixo é isomórfico a um autômato de equação definido por Antimirov. Além disso, damos um NFA chamado um autômato de equação unificada juntando dois NFAs. Assim, o número de estados de um autômato de equação unificada pode ser menor que o de um autômato de equação.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -