La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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 Une nouvelle construction d'automates finis utilisant un préfixe et un suffixe d'expressions régulières

Hiroaki YAMAMOTO, Hiroshi FUJIWARA

  • Vues en texte intégral

    0

  • Citer

Résumé:

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.

Publication
IEICE TRANSACTIONS on Information Vol.E104-D No.3 pp.381-388
Date de publication
2021/03/01
Publicisé
2020/11/09
ISSN en ligne
1745-1361
DOI
10.1587/transinf.2020FCP0010
Type de manuscrit
Special Section PAPER (Special Section on Foundations of Computer Science — New Trends of Theory of Computation and Algorithm —)
Catégories

Auteurs

Hiroaki YAMAMOTO
  Shinshu University
Hiroshi FUJIWARA
  Shinshu University

Mots-clés

Table des matières