A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

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 Uma nova construção de autômatos finitos usando um prefixo e um sufixo de expressões regulares

Hiroaki YAMAMOTO, Hiroshi FUJIWARA

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

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.

Publicação
IEICE TRANSACTIONS on Information Vol.E104-D No.3 pp.381-388
Data de publicação
2021/03/01
Publicitada
2020/11/09
ISSN online
1745-1361
DOI
10.1587/transinf.2020FCP0010
Tipo de Manuscrito
Special Section PAPER (Special Section on Foundations of Computer Science — New Trends of Theory of Computation and Algorithm —)
Categoria

autores

Hiroaki YAMAMOTO
  Shinshu University
Hiroshi FUJIWARA
  Shinshu University

Palavra-chave