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
이 문서에서는 정규식을 비결정적 유한 자동 장치(간단히 NFA)로 변환하는 새로운 방법을 제시합니다. 허락하다 r 정규 표현식이 되어 보자 M 톰슨 자동인형이 되어 보세요 r. 먼저 단어의 접두사와 접미사를 나타내는 두 가지 유형의 표현을 할당하여 정의된 레이블이 지정된 Thompson 자동 장치를 소개합니다. L(r) 각 주에 M. 그런 다음 레이블이 지정된 Thompson 자동 장치로 구성된 새로운 ϵ-free NFA를 제공합니다. 이러한 NFA를 호출합니다. 접두사 방정식 자동 장치 and 접미사 방정식 자동 장치. 우리는 접미사 방정식 자동 장치가 Antimirov가 정의한 방정식 자동 장치와 동형임을 보여줍니다. 또한 우리는 NFA라는 NFA를 제공합니다. 통합 방정식 자동 장치 두 개의 NFA에 가입함으로써. 따라서 통합 방정식 자동 장치의 상태 수는 방정식 자동 장치의 상태 수보다 작을 수 있습니다.
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.
부
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
부
@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},}
부
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 -