Derivatives for Enhanced Regular Expressions
Regular languages are closed under a wealth of formal language operators. Incorporating such operators in regular expressions leads to concise language specifications, but the transformation of such enhanced regular expressions to finite automata becomes
- PDF / 285,594 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 50 Downloads / 239 Views
Abstract. Regular languages are closed under a wealth of formal language operators. Incorporating such operators in regular expressions leads to concise language specifications, but the transformation of such enhanced regular expressions to finite automata becomes more involved. We present an approach that enables the direct construction of finite automata from regular expressions enhanced with further operators that preserve regularity. Our construction is based on an extension of the theory of derivatives for regular expressions. To retain the standard results about derivatives, we develop a derivability criterion for the compatibility of the extra operators with derivatives. Some derivable operators do not preserve regularity. Derivatives provide a decision procedure for the word problem of regular expressions enhanced with such operators. Keywords: Automata and logic
1
· Regular languages · Derivatives
Introduction
Brzozowski derivatives [4] and Antimirov’s partial derivatives [2] are well-known tools to transform regular expressions to automata and to define algorithms for equivalence and containment on them [1,9]. Brzozowski’s automaton construction relies on the finiteness of the set of iterated derivatives when considered up to similarity (commutativity, associativity, and idempotence for union). Derivatives had quite some impact on the study of algorithms for regular languages on finite words and trees [5,12]. While derivative-based algorithms have been deprecated for performance reasons [16], there has been renewed interest in the study of derivatives and partial derivatives. On the practical side, Owens and coworkers [11] report a functional implementation that revives many features. Might and coworkers [10] implement parsing for context-free languages using derivatives. A common theme on the theory side is the study of derivative structures for enhancements of regular expressions. While Brzozowski’s original work covered extended regular expressions, partial derivatives were originally limited to simple expressions without intersection and complement. It is a significant effort to define partial derivatives for extended regular expressions [5]. Derivatives have also been used to study various shuffle operators for applications in modeling concurrent programs [13]. Later extensions consider forkable expressions with a new operator that abstracts process creation [14]. c Springer International Publishing Switzerland 2016 Y.-S. Han and K. Salomaa (Eds.): CIAA 2016, LNCS 9705, pp. 285–297, 2016. DOI: 10.1007/978-3-319-40946-7 24
286
P. Thiemann
Caron and coworkers [6] study derivatives for multi-tilde-bar expressions. The tilde (bar) operator adds (removes) ε from a language. Multi-tilde-bar applies to a list of languages and (roughly) defines a selective concatenation operation that can be configured to include or exclude certain languages of the list. Champarnaud and coworkers [8] consider derivatives of approximate regular expressions (ARE). AREs extend regular expressions with a family of unary operators F
Data Loading...
