Development of An Efficient Tool to Convert Regular Expressions to NFA

Abstract

In the computing theory, while the term “Language” specifies the string set, the term “Regular Expressions” means the notation that builds, creates and generates these languages. Also, the term “Regular Expressions” creates the characters that structure and compose, which refers to the given strings, in order to search patterns for sample matching. In this context, this article tries to show how to convert “Regular Expressions” that is made up of characters into Nondeterministic Finite Automata (NFA), which is a character matching and character searching tool, by giving related algorithms and methods with their explanations in detail. Moreover, in this study, a new and efficient tool has been designed and developed in order to convert regular expressions to NFA. By the contribution of this application, an original conversion tool will have been gained in the computation area for benefiting it. As a natural result of this, an original NFA modelling tool will have been placed in the literature.

Keywords

• Computing theory
• regular expressions
• NFA
• modelling

References

1. Horswill, I. (2008). What is computation? Obtained from https://users.cs.northwestern.edu/~ian/What%20is%20computation.pdf (Last access on 19th August 2021)
2. Harvey, B. (1997). Computer science logo style (1st ed.). USA: The MIT Press.
3. Dlugosch, P., Brown, D., Glendending, P., Leventhal, M., & Noyes, H. (2014). An efficient and scalable semiconductor architecture for parallel automata processing. IEEE Transactions on Parallel and Distributed Systems, 25(12), 3088-3098.
4. Lucas, S. M., & Reynolds, T. J. (2005). Learning deterministic finite automata with a smart state labeling evolutionary algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(7), 1063-1074.
5. Holzer, M., & König, B. (2004). On deterministic finite automata and syntactic monoid size. Theoretical Computer Science, 327(3), 319-347.
6. Yang, L. Karim, R., Ganapathy, V., & Smith, R. (2011). Fast, memory-efficient regular expression matching with NFA-OBDDs. Computer Networks, 55(15), 3376-3393.
7. Pao, D, Lam, N., & Cheung, R. A memory-based NFA regular expression match engine for signature-based intrusion detection. Computer Communications, 36(10-11), 1255-1267.
8. Hopcroft E., Motwani, R., & Ullman, D. (2007). Introduction to automata theory, languages, and computation (3rd ed.). Britain: Pearson.

9. Konstantinidis, S. (2007). Computing the edit distance of a regular language. Information and Computation, 205(9), 1307-1316.
10. Owens, S., Reppy, J., & Turon, A. (2009). Regular-expression derivatives re-examined. Journal of Functional Programming, 19(2), 173-190.
11. Lee, T. (2009). Hardware architecture for high-performance regular expression matching. IEEE Transactions on Computers, 58(7), 984-993.
12. Kumar, S., Dharmapurikar, S., Yu, F., Crowley, P., & Turner, J. (2006). Algorithms to accelerate multiple regular expressions matching for deep packet inspection. Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, 339-350.
13. McNaughton, R., & Yamada, H. (1960). Regular expressions and state graphs for automata. IRE Transactions on Electronic Computers, 9(1), 39-47.
14. Kurai, R., Yasuda, N., Arimura, H., Nagayama, S., & Minato, S. (2014). Fast regular expression matching based on dual Glushkov NFA. Proceedings of PSC 2014, 3-16.
15. Thompson, K. (1968). Programming techniques: Regular expression search algorithm. Communications of the ACM, 11(6), 419-422.
16. Berry, G., & Sethi, R. (1986). From regular expressions to deterministic automata. Theoretical Computer Science, 48(1), 117-126.
17. Chang, C. (1992). From regular expressions to DFA’s using compressed NFA’s. PhD Thesis, New York University, New York.
18. Antimirov, V. (1996). Partial derivatives of regular expressions and finite automaton constructions. Theoretical Computer Science, 155(2), 291-319.
19. Brzozowski, J. A. (1964). Derivatives of regular expressions. J. ACM 11(4), 481-494.
20. Kleene, S. C. (1956). Representation of events in nerve nets and finite automata. In Automata Studies, Ann. Math. Stud. No. 34. Princeton U. Press, Princeton, N. J., 3-41.
21. IBM Corp. IBM 7094 principles of operation. File No. 7094-01, Form A22-6703-1.
22. Kuno, S., & Oettinger, A. G. (1962). Multiple-path syntactic analyzer. Proc. IFIP Congress, Munich.