A New Method for Translating NFA into DFA

Yuan Bin Cheng

doi:10.4028/www.scientific.net/AMM.325-326.1754

Paper Titles

Wireless Mesh Network Technical Security Performance Analysis
p.1738

An Efficient P2P Overlay Network Model Based on Clustering
p.1742

A MATLAB-Based Study on the Realization and Approximation Performance of RBF Neural Networks
p.1746

Research of Data Model in Engineering Flight Simulation Platform Based on Meta-Data
p.1750

A New Method for Translating NFA into DFA
p.1754

A Mapping Simulation of Code Generation for Partitioned System
p.1759

PPSim: A Cycle-Accurate Simulator for PowerPC Instruction Set
p.1766

A New P2P Streaming Media VOD System Based on Window
p.1770

Design and Implementation of an Active RFID System Based on Bluetooth Low Energy
p.1774

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 325-326A New Method for Translating NFA into DFA

A New Method for Translating NFA into DFA

Abstract:

It is important in theory and practice to translate a NFA into DFA. So far, subset construction is the most popular method. The method, however, needs import a dummy input ε and ε-closure and has a complicated computing procedure. In this paper, a new method to translate a NFA into DFA straightly is described. The new method needn’t import a dummy input ε and ε-closure, it accords to the original NFA state graph or state shift table to translate a NFA into DFA straightly.

You might also be interested in these eBooks

Manufacturing Engineering and Process II

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 325-326)

Pages:

1754-1758

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.325-326.1754

Citation:

Cite this paper

Online since:

June 2013

Authors:

Yuan Bin Cheng

Keywords:

Convert Straightly, Deterministic Finite Automata, Finite Automata, Nondeterministic Finite Automata, Subset Construction

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] ZHANG Wei, XUE Yibo, TIAN Song, Multiple regular expression matching hardware architecture[J], Journal of Tsinghua University (Science and Technology) 2009.vol49, No.10, pp.132-135

Google Scholar

[2] Zhou Jingye, Zhang Jifu Compiling Principle[M] Wuhan University of Technology Press 2003. 8

Google Scholar

[3] MAO Hong-mei, NIE Cheng-qi A Method of Alteration from NFA to Minimum-state DFA [J] Computer and Modernization 2004.10 pp.6-7

Google Scholar

[4] ZHOU Qi-hai Automata Transform Algorithm for "NFA→FA→GFA" [J] . Journal of University of Electronic Science and Technology of China 2005.3,pp.363-365

Google Scholar

[5] SUN Yu-Qiang, LIU San-Yang, WANG Ming-Fei, ZOU Ling. Parallel Conversion of NFA to DFA [J] Computer Science, 2006.10 pp.293-295

Google Scholar

[6] Gertjan van Noord Treatment of Epsilon Moves in SubsetConstruction[J] . Computational Linguistics , 2000.1 pp.61-76

Google Scholar

[7] REN Ping-hong, CAO Bao-xiang,CHEN Chu, YU Ji-guo An Optimized Algorithm for Transition from NFA to DFA Based on Subset Construction Method[J] Computer Technology and Development 2011.1 pp.70-73

Google Scholar