Title: Computation of regular expression derivatives

Authors: N. Murugesan; O.V. Shanmuga Sundaram

Addresses: Department of Mathematics, Government Arts College (Autonomous), Coimbatore – 641 018, India ' Department of Mathematics, Sree Saraswathi Thyagaraja College, Pollachi, Tamil Nadu, India

Abstract: The conversion of regular expressions into finite state automata and finite state automata into regular expression is an important area of research in automata theory. The notion of derivatives of regular expressions has been introduced to make the construction of finite state automata from regular expressions in a natural way. Recently, a general structure has been proposed to find the derivatives of regular expressions to reduce the difficulties arising out of the earlier methods. In this paper, some properties of the derivatives of regular expressions, the quotient language, and how the derivatives are found through a general structure, have been discussed in detail.

Keywords: regular expressions; Brzozowski's derivatives; Boolean formulas; support; regular expression derivatives; finite state automata; automata theory.

DOI: 10.1504/IJCSM.2016.077858

International Journal of Computing Science and Mathematics, 2016 Vol.7 No.3, pp.201 - 211

Accepted: 31 Mar 2016
Published online: 17 Jul 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article