검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

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

A New Finite Automata Construction Using a Prefix and a Suffix of Regular Expressions 정규식의 접두사와 접미사를 사용한 새로운 유한 오토마타 구성

Hiroaki YAMAMOTO, Hiroshi FUJIWARA

  • 조회수

    0

  • 이것을 인용

요약 :

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

발행
IEICE TRANSACTIONS on Information Vol.E104-D No.3 pp.381-388
발행일
2021/03/01
공개일
2020/11/09
온라인 ISSN
1745-1361
DOI
10.1587/transinf.2020FCP0010
원고의 종류
Special Section PAPER (Special Section on Foundations of Computer Science — New Trends of Theory of Computation and Algorithm —)
범주

작성자

Hiroaki YAMAMOTO
  Shinshu University
Hiroshi FUJIWARA
  Shinshu University

키워드